# Foremost Walks and Paths in Interval Temporal Graphs +
## 5 Min-Wait Foremost Walks in Interval Temporal Graphs
### Properties of \(mwf\) Walks
Therefore, there is no benefit of extending \(A\) at \(t^{\prime}\)  
If the walk \(A\) arriving at \(u\) is extended from \(u\) to \(v\) using the edge \((u,v)\) at time \(t_{dep}\geq t_{A}\) in a departure interval \(I_{1}(s_{1},e_{1},\lambda_{1})\), then \(A\) may need to be extended again using the edge \((u,v)\) in a subsequent interval \(I_{2}(s_{2},e_{2},\lambda_{2})\) where (\(s_{2}>e_{1}\)) if one of the following is true  
1. \(s_{2}+\lambda_{2}<t_{dep}+\lambda_{1}\)
2. \(\lambda_{2}>\lambda_{1}\)  
Proof. : \(t_{A}\leq e_{1}\) as \(A\) can be extended in \(I_{1}\). Therefore, the earliest time at which \(A\) can be extended in \(I_{2}\) is \(s_{2}\). It need not be extended at any other time in \(I_{2}\) due to Theorem 4. Let the extension of \(A\) obtained by extending in \(I_{1}\) be \(A1\) and that obtained by extending in \(I_{2}\) be \(A2\). 1. If \(s_{2}+\lambda_{2}<t_{dep}+\lambda_{1}\), it means \(t_{A2}<t_{A1}\); therefore, \(A\) will need to be extended at \(s_{2}\) so we do not miss any opportunities of further expansion in intervals of departure available at \(v\) at a time \(t\), such that \(s_{2}+\lambda_{2}\leq t<t_{dep}+\lambda_{1}\). 2. 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}\]3 (14) \[(t_{B}-t_{A}+w_{A})>w_{B}\]4 (15) Comparing \(A1\) and \(A2\) at \(v\), we see that \(s_{2}+\lambda_{2}\geq t_{dep}+\lambda_{1}\) as otherwise, condition \(1\) would be true. Therefore, we have: \[(t_{B}-t_{A}+w_{A})>w_{B}\]5 (16) Let \(e=t_{A2}-t_{A1}+w_{A1}\). Evaluating \(e\) using Equation (16) and substituting for \(w_{A1}\) from Equation (14), we obtain \[(t_{B}-t_{A}+w_{A})>w_{B}\]6 (17) Substituting \(w_{A2}\) from Equation (15) into Equation (17), we obtain: \[(t_{B}-t_{A}+w_{A})>w_{B}\]7 (18) We know that for \(A2\) to survive being dominated by \(A1\), we need Equation (19) to be true \[(t_{B}-t_{A}+w_{A})>w_{B}\]8 (19) Therefore, for Equation (19) to be true, \(\lambda 2>\lambda 1\), otherwise \(A2\) will be dominated by \(A1\). Therefore, unless \(1\) or \(2\) is true, there is no benefit of extending in interval \(I_{2}\). This can also be seen from the example of \[(t_{B}-t_{A}+w_{A})>w_{B}\]9 There are two intervals on the edge \((u,v)\) with \(I1(2,6,12)\) and \(I2(10,20,5)\). \(A\) departs at \(2\) and then does not need to depart in \(I2(10,20,5)\), as none of the conditions of Theorem 4.1 is satisfied. \(A^{\prime}\) departs at \(4\) in \(I1(2,6,12)\) but needs to depart in \(I2(10,20,5)\) again as condition \(1\) is satisfied. **Theorem 13**: _If walk \(A\) arriving at \(u\) is extended from \(u\) to \(v\) using the edge \((u,v)\), it should always be extended at \((t_{dep},intv1 Id)=f(u,v,t_{A})\), where \(f(u,v,t)\) is the next function referred to in Section 4.1 and described in [9; 13]._  
From Theorem 11, a given walk departing in a departure interval \(I\) on an edge \((u,v)\) should always depart at the earliest possible departure time in \(I\). Further, as per the conditions stated in Theorem 12, it is evident that, for any two available departure intervals \(I_{1}(s_{1},e_{1},\lambda_{1})\) and \(I_{2}(s_{2},e_{2},\lambda_{2})\) where \(e_{1}\leq s_{2}\) on an edge \((u,v)\), a walk \(A\) terminating at \(u\) such that \(t_{A}\leq e_{1}\) should always depart in \(I_{1}\) and whether or not it departs in \(I_{2}\) is determined by the conditions specified in the theorem.