<aside> 🌐

Outdated page — the Temporal Graph Wiki has moved. Read the wiki on temporalgraph.wiki.

</aside>

Temporal exploration asks whether an agent can visit all vertices—or, in a separate variant, traverse all edges—by following edges when they are available. The central questions are whether an exploration exists, how long it takes, and how efficiently it can be found.

In a static connected undirected graph, a walk can visit every vertex: traversing a spanning tree uses at most $2n-2$ edge traversals, or $2n-3$ when the endpoint is free and $n\geq2$. Computing a shortest covering walk is a different, potentially hard optimization problem.

In a temporal graph, a connected footprint does not automatically guarantee a feasible visiting order. Consequently, one often studies the special case where every snapshot is connected. Waiting at a vertex is usually allowed but it consumes time.

History of temporal exploration