Temporal trips or journeys, also called time-respecting paths, are a fundamental concept for computational problems on temporal graphs.
Reachability,Temporal Spanners,Temporal Connected Components,Flows and Cuts,Temporal Separators,Spreading Processes,Exploration,Gossip Theory,Centrality Metrics,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