# Foremost Walks and Paths in Interval Temporal Graphs +
## 5 Min-Wait Foremost Walks in Interval Temporal Graphs  
### Properties of \(mwf\) Walks  
In this section, we describe properties of \(mwf\) walks that are used later in the section for developing single-source all-destinations \(mwf\) walks algorithm and the correctness proof of our \(mwf\) algorithm. Some of the terminology we use is given below. 1. For a walk \(X\), \(t_{X}\) denotes its arrival time at its terminating vertex \(v\) and \(w_{X}\) denotes the total wait time accumulated by \(X\) along its way from \(s\) to \(v\). 2. Comparing any two walks \(X\) and \(X^{\prime}\) w.r.t \(mwf\) arrival at a vertex \(v\), \(X\) is said to be _the same or better_ than \(X^{\prime}\) if \(t_{X}\leq t_{X^{\prime}}\) and \(w_{X}\leq w_{X^{\prime}}\). 3. A walk from \(s\) to \(v\) via some vertex \(u\) is denoted as \(W(s,u,v)\). 4. A walk \(X\) from \(s\) to \(u\) that is extended further to obtain a walk \(W(s,u,v)\) is a prefix walk denoted by \(X=Pre(W(s,u,v))\). Definition 1: Walk dominance--for any two walks \(A\) and \(A^{\prime}\) from \(s\) to \(u\), \(A\) is said to dominate over \(A^{\prime}\) if, for any walk \(W(s,u,v)\) where \(A^{\prime}=Pre(W(s,u,v))\), \(A^{\prime}\) can always be replaced by \(A\) to produce a _same-or-better_ walk \(W^{\prime}(s,u,v)\) w.r.t \(mwf\) arrival at \(v\)  
Theorem 3.2: _If there are two walks, \(A(t_{A},w_{A})\) and \(A^{\prime}(t_{A^{\prime}},w_{A^{\prime}})\), that arrive at a vertex \(u\), such that \(t_{A}\leq t_{A^{\prime}}\), then if \(((t_{A^{\prime}}-t_{A}+w_{A})\leq w_{A^{\prime}})\) then \(A\) dominates \(A^{\prime}\)._  
Proof: We have:  
\[(t_{A^{\prime}}-t_{A}+w_{A})\leq w_{A^{\prime}} \tag{1}\]  
Let the departure time of \(A^{\prime}\) for any onward walk from \(u\) be \(t_{dep}\geq t_{A^{\prime}}\). Since \(t_{A}\leq t_{A^{\prime}}\), \(t_{dep}\geq t_{A}\), therefore, \(A\) can also depart vertex \(u\) at \(t_{dep}\). If \(A^{\prime}\) departs at \(t_{dep}\), the wait time accumulated by the time of departure is \(w^{\prime}=w_{A^{\prime}}+t_{dep}-t_{A^{\prime}}\). If \(A\) departs at \(t_{dep}\), the wait time accumulated by the time of departure is \(w=w_{A}+t_{dep}-t_{A}\). Due to Equation (1) \(w^{\prime}\geq w\). Hence, if \(A^{\prime}\) is replaced by \(A\), then any possible extension of \(A^{\prime}\) can still depart at the same time and would have accumulated an equal or less wait time by the time it departs from \(u\). Therefore, \(A^{\prime}\) can always be replaced by \(A\) in any possible extension of \(A^{\prime}\) to obtain a _same-or-better_ walk. Theorem 3.2: _For identifying non-dominated walks among all the walks arriving at a vertex \(u\), all walks may be arranged in an increasing order of arrival time at vertex \(u\) and only adjacent walks need be compared for dominance._  
Proof: If there are three walks \((A,B,C)\) terminating at \(u\) with arrival times \((t_{A}\leq t_{B}\leq t_{C})\), we need to show that it is sufficient to compare only the adjacent walks to find and retain the dominant walks terminating at \(u\). This follows from the following two conditions:  
1. If \(B\) survives \(A\) (is not dominated by \(A\)), then comparing \(C\) with \(B\) should have the same result as comparing \(C\) with \(A\). In other words 1. If \(C\) survives \(B\), it also survives \(A\). 2. If \(C\) is dominated by \(B\), it is also dominated by \(A\). 2. If \(A\) dominates \(B\) and \(B\) dominates \(C\), then \(A\) also dominates \(C\). Therefore, it does not matter in which order the walks are compared. Both \(B\) and \(C\) will be eliminated. 1. We are given \(B\) is not dominated by \(A\) or survives \(A\). Based on the dominance criteria of Equation (1) we obtain Equation (2) for \(B\) surviving \(A\) \[(t_{B}-t_{A}+w_{A})>w_{B}\] (2) 2.