Temporal trips or journeys, also called time-respecting paths, are a fundamental concept for computational problems on temporal graphs.
They form the basis of Reachability which is closely related to Temporal Spanners and the analysis of Temporal Graph Settings; they are necessary to define Temporal Connected Components and Flows and Cuts as well as Temporal Separators. These trips enable Spreading Processes which are closely related to Exploration and Gossip Theory; and they are necessary to define Centrality Metrics like the Diameter.
There are three types of journeys.
<aside> <img src="/icons/report_orange.svg" alt="/icons/report_orange.svg" width="40px" />
A temporal path is a time-respecting sequence of adjacent temporal edges which does not revisit vertices, i.e.,
…
</aside>
<aside> <img src="/icons/report_orange.svg" alt="/icons/report_orange.svg" width="40px" />
A temporal trail is a time-respecting sequence of adjacent temporal edges which does not revisit (static) edges, i.e.,$(v_0,v_1,t_1),(v_1,v_2,t_2),\dots,(v_{\ell-1},v_\ell,t_\ell)$ with $(v_{i-1},v_i,t_i)\in \mathcal{E}$, $t_i\leq t_{i+1}$, and $\{v_{i-1},v_i\}\neq \{v_{j-1},v_j\}$ for all $i\neq j$.
</aside>
<aside> <img src="/icons/report_orange.svg" alt="/icons/report_orange.svg" width="40px" />
A temporal walk is a time-respecting sequence of adjacent temporal edges, i.e.,$(v_0,v_1,t_1),(v_1,v_2,t_2),\dots,(v_{\ell-1},v_\ell,t_\ell)$ with $(v_{i-1},v_i,t_i)\in \mathcal{E}$ and $t_i\leq t_{i+1}$.
If we require the labels to be strictly increasing $t_i\leq t_{i+1}$
</aside>
Single source ‘shortest’
Counting