Anne-Sophie Himmel (TU Berlin)

Shortest paths are a fundamental concept in classical graph theory.
Within the realm of temporal graphs - graphs that change over time - the
optimization criterion of a shortest path is no longer unique as a
result of the addition of a time component. We survey various
optimization criteria, some well studied in the literature (e.g.
earliest arrival time), others comparatively neglected thus far (e.g.
minimum waiting time). We present properties of optimal temporal walks
and discuss their algorithmic implications. We study the efficiency of
algorithms computing single-source, single-sink, and all-pairs shortest
path for different variants of temporal graphs and optimization
criteria. We also consider parameterized problem variants. In addition
to lower bounds, the parameterization by vertex cover number and
treewidth of the underlying (classical) graph are examined.

Back to the research colloquium site.