TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 05.12.2019 (2)

isti-logo

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.

 

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

Back to the research colloquium site.

To top

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe