# Foremost Walks and Paths in Interval Temporal Graphs +
## 5 Min-Wait Foremost Walks in Interval Temporal Graphs
### Departure from Source Vertex \(s\)  
All walks that start from a source vertex \(s\) have a wait time of \(0\), as there is no wait accumulated at the source vertex. Therefore, for any available departure interval on an edge \((s,x)\), we should be extending at every possible instance of time in this departure interval. Theorems 11 and 12 do not apply to walks departing from the source vertex \(s\), as these theorems assume that there is an extra wait accumulated if a walk \(A\) is extended at a later time from the departing vertex \(u\). However, this is not true when \(u=s\) as the wait time at \(s\) is always \(0\). This implies, we may assume that \(mwf\) walks do not have a cycle that involves \(s\) as such cycles can be removed from the walk without increasing either the total wait time or the arrival time at the destination. From the source vertex \(s\), walks may depart at every departure instance available to find \(mwf\) walks. To account for this, we introduce the concept of a _walk class_.  
**Definition 2**: _A walk class \((ws,we,u)\) is a set of walks that arrives at the vertex \(u\) with a wait time of \(0\). The first walk in this set arrives at \(ws\) and the last one arrives at \(we\), where \(we>ws\). There is a walk in the walk class at every instance of time in the range \([ws,we]\) and each of these walks has the same total wait time, which is \(0\). This can be seen in Figure 10._  
For every departure interval denoted by \(I(start,end,\lambda)\) where \(end>start\) on an edge \((s,x)\), we need to generate a walk class, ranging from the \(start\) to \(end\), with travel time as \(\lambda\) and a wait time of \(0\). Once the walks in the walk class arrive at the neighbor \(x\), Theorems 11 and 12 apply to each walk in the class.  
**Theorem 14**: _Each walk in a walk class survives the walk, if any, that arrives before it._  
Figure 10: Example of a walk class.  
Figure 9: Example of departure in next intervals.  
Proof.: This is easy to see from Equation (1), as these walks have the same wait time but different arrival times.  
Theorem 4.1: _If two walk classes \(WC_{1}\) and \(WC_{2}\) arrive at a vertex \(u\), there is no dominance to be considered._  
Proof.: This follows from Equation (1), as the wait times of all walks is 0. When they overlap, one of them may be discarded. When they do not overlap, both can be retained.  
When a walk class, \(WC(ws,we)\), terminates at a vertex \(u\), if some portion of it overlaps with a departure interval \(I(s,e,\lambda)\) from \(u\) to a neighbor \(v\), the set of walk instances \(x\) in the walk class \(WC\) such that \(s\leq t_{x}\leq e\) can be immediately extended to the neighbor \(v\) without any additional wait at \(u\) into a new walk class arriving at \(v\) as \(WC^{\prime}(ws^{\prime},we^{\prime})\). Therefore, each walk in \(WC^{\prime}(ws^{\prime},we^{\prime})\) also has a wait time of 0. If there is no overlap with a departure interval from \(u\) to \(v\), then only the walk instance at \(we\) needs to be extended to \(v\) due to Theorems 4.1 and 4.1.  
For the \(mwf\) problem, redundant intervals as described in [13] for the foremost, min-hop, fastest problems are not redundant and need to be retained. Such intervals, however, are redundant for \(mhf\) problems, as noted in Section 4.1  
This is illustrated with the example of Figure 11. The min-wait foremost \(mwf\) walk from \(s\) to \(c\) would benefit by departing from the vertex \(s\) at 0, instead of waiting for the next faster interval that becomes available for departure at 2 and reaches \(a\) at 4. Departing at 0 from \(s\) reaches \(a\) at 5. In this case, the \(mwf\) walk would be \(W_{mwf}=(s,0,a,7,b,1,c)\) arriving at vertex \(c\) at time 9 with a wait time of 0.