TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 05.12.2019 (2)


Page Content

to Navigation

Efficient Computation of Optimal Temporal Walks under Waiting-Time Constraints

Anne-Sophie Himmel (TU Berlin)


Node connectivity plays a central role in temporal network analysis. We provide a comprehensive study of various concepts of walks in temporal graphs, that is, graphs with fixed vertex sets but edge sets changing over time.  Importantly, the temporal aspect results in a rich set of optimization criteria for ``shortest'' walks. Extending and significantly broadening state-of-the-art work of Wu et al. [IEEE TKDE 2016], we provide an quasi-linear-time algorithm for computing shortest walks that is capable to deal with various optimization criteria and any linear combination of these. A central distinguishing factor to Wu et al.'s work is that our model allows to, motivated by real-world applications, respect waiting-time constraints for vertices, that is, the minimum and maximum waiting time allowed in intermediate vertices of a walk. Moreover, other than Wu et al. our algorithm also allows to search for walks that pass multiple edges in one time step, and it can optimize a richer set of optimization criteria. Our experimental studies  indicate that our richer modeling can be achieved without significantly worsening the running time when compared to Wu et al.'s algorithms.


Anne-Sophie Himmel
TEL 512

Back to the research colloquium site.

To top


Quick Access

Schnellnavigation zur Seite über Nummerneingabe