Enumeration: Generate all feasible substructures (e.g. spanning trees of a static graph).

<aside> 💡

Enumeration problem.

Generate all feasible substructures. Typical complexity classes:

Extension problem. Given a set of static edges $E'\subseteq E(G)$ does there exist at least one temporal spanner containing $E'$?

</aside>

setting: directed | strict and nonstrict

Given a directed temporal graph $\mathcal{G}=(V,E,\lambda)$, a subset of sources $S=\{s_1,\dots,s_k\}\subseteq V(G)$, a subset of static edges $E'\subseteq E(G)$ is a temporal spanner for $S$ if every source $s\in S$ can reach every vertex in the graph using only edges in $E'$.

image.png