# Foremost Walks and Paths in Interval Temporal Graphs +
## 5 Min-Wait Foremost Walks in Interval Temporal Graphs
### Properties of \(mwf\) Walks
When \(C\) survives \(B\), we have \[(t_{C}-t_{B}+w_{B})>w_{C}\] (3) We are to prove that \(C\) also survives \(A\) \[(t_{C}-t_{A}+w_{A})>w_{C}\] (4) Adding Equations (2) and (3) yields (4)When \(C\) is dominated by \(B\), Equation (1) gives \[(t_{C}-t_{B}+w_{B})\leq w_{C}\] (5) Replacing \(w_{B}\) from Equation (2) in Equation (5), we obtain \[(t_{C}-t_{A}+w_{A})\leq w_{C}\] (6) Therefore, \(A\) also dominates \(C\). This proves that, when \(B\) is not dominated by \(A\), then comparing \(C\) with \(B\) has the same result as comparing \(C\) with \(A\). 2. Here, we prove that if \(A\) dominates \(B\) and \(B\) dominates \(C\), then \(A\) also dominates \(C\). Since \(A\) dominates \(B\) we have \[(t_{B}-t_{A}+w_{A})\leq w_{B}\] (7) For \(B\) dominates \(C\) we have Equation (5). The two Equations (5) and (7), can be added together to obtain Equation (6), which states that \(A\) dominates \(C\). Therefore, when \(A\) dominates \(B\) and \(B\) dominates \(C\), regardless of the order in which the adjacent walks are compared, both \(B\) and \(C\) will be eliminated. Hence, for any three walks \(A\), \(B\), and \(C\) with \(t_{A}\leq t_{B}\leq t_{C}\), only adjacent walks need to be compared to remove dominated walks and retain non-dominated walks. When applied transitively to all walks arriving at \(u\), we see that if all the arriving walks are arranged in non-decreasing order of their arrival times, only adjacent walks need to be compared to eliminate the dominated walks and retain the non-dominated walks. **Theorem 10**. : _For any two walks \(A\) and \(B\) arriving at a vertex \(u\), where \(t_{B}>t_{A}\), if \(B\) is not dominated by \(A\) as per the dominance criteria (1), then for any departure time \(t\) available on an outgoing edge \((u,v)\) such that \(t\geq t_{B}\), \(A\) need not be considered for expansion._  
Proof. : Let \(A^{\prime}\) be the walk obtained by extending \(A\) from \(u\) to a neighbor \(v\) at time \(t\geq t_{B}\). Similarly, \(B^{\prime}\) is obtained by extending \(B\) on \((u,v)\) at \(t\geq t_{B}\). Assuming \(\lambda\) as the travel time when departing at \(t\) on the edge \((u,v)\), we have the following:  
\[t_{A^{\prime}}=t+\lambda;w_{A^{\prime}}=w_{A}+(t-t_{A}) \tag{8}\]  
\[t_{B^{\prime}}=t+\lambda;w_{B^{\prime}}=w_{B}+(t-t_{B}) \tag{9}\]  
Therefore, we have \(t_{A^{\prime}}=t_{B^{\prime}}\). In addition, since \(B\) is not dominated by \(A\), we have  
\[t_{B}-t_{A}+w_{A}>w_{B} \tag{10}\]  
From Equations (8)-(10), we have \(w_{B^{\prime}}<w_{A^{\prime}}\). This means that extending \(A\) at \(t\geq t_{B}\) is not beneficial, as it will be dominated by \(B^{\prime}\). **Theorem 11**. : _In order to find \(mwf\) walks, if walk \(A\) arriving at \(u\) is extended from \(u\) to \(v\) using an edge \((u,v)\) at time \(t_{dep}\geq t_{A}\) in a departure interval \(I(s,e,\lambda)\), then there is no benefit to extending \(A\) using the same edge \((u,v)\) in the same interval \(I(s,e,\lambda)\) at a time \(t^{\prime}\) where \(t^{\prime}>t_{dep}\)._  
Proof. : Let the extension of \(A\) from \(u\) to \(v\) by departing at \(t_{dep}\) be \(A1\). Let the extension to \(v\) obtained by departing at \(t^{\prime}\) be \(A2\). We have the following two equations for the arrival and wait times of \(A1\) and \(A2\), respectively. \[(t_{B}-t_{A}+w_{A})>w_{B}\]0  
\[(t_{B}-t_{A}+w_{A})>w_{B}\]1Clearly, \(t_{A1}<t_{A2}\) as \(t_{dep}<t^{\prime}\). Further, substituting \(t_{A2},t_{A1},w_{A1}\) from Equations (11) and (12) in expression \(t_{A2}-t_{A1}+w_{A1}\), we obtain  
\[(t_{B}-t_{A}+w_{A})>w_{B}\]2  
From the dominance criterion of Equation (1), we conclude that \(A1\) dominates \(A2\). This means that if we extend \(A\) at \(t_{dep}\) and at \(t^{\prime}>t_{dep}\) in the departure interval \(I(s,e,\lambda)\) using the edge \((u,v)\) to obtain \(A1\) and \(A2\), respectively, \(A2\) will be dominated at \(v\) by \(A1\).