Efficient computation of optimal temporal walks under waiting-time constraints

Applied Network Science

Anne-Sophie Himmel¹  André Nichterlein¹  Rolf Niedermeier¹  Matthias Bentert¹ 

[1] Technische Universität Berlin, Faculty IV, Algorithmics and Computational Complexity, Berlin, Germany;

关键词: Temporal networks;    Temporal paths;    Shortest path computation;    Waiting policies;    Infectious disease spreading;   

DOI  :  10.1007/s41109-020-00311-0

来源: Springer

【 摘 要 】

Node connectivity plays a central role in temporal network analysis. We provide a broad study of various concepts of walks in temporal graphs, that is, graphs with fixed vertex sets but arc sets changing over time. Taking into account the temporal aspect leads to a rich set of optimization criteria for “shortest” walks. Extending and broadening state-of-the-art work of Wu et al. [IEEE TKDE 2016], we provide an algorithm for computing shortest walks that is capable to deal with various optimization criteria and any linear combination of these. It runs in O(|V|+|E|log|E|) time where |V| is the number of vertices and |E| is the number of time-arcs. 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 subsequent time-arcs in one time step, and it can deal with 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.

【 授权许可】

CC BY