TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 19.04.2018

isti-logo

Page Content

to Navigation

Algorithmic Investigations into Temporal Paths

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.

 

 

Date
Speaker
Location
Language
19.04.2018
16:15
Anne-Sophie Himmel
TEL 512
English

Back to the research colloquium site.

To top

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe