Efficient computation of optimal temporal walks under waiting-time constraints
- PDF / 1,113,015 Bytes
- 26 Pages / 595 x 794 pts Page_size
- 39 Downloads / 210 Views
Applied Network Science
RESEARCH
Open Access
Efficient computation of optimal temporal walks under waiting-time constraints Matthias Bentert* , Anne-Sophie Himmel, André Nichterlein and Rolf Niedermeier An extended abstract of this work appeared in the proceedings of the 8th International Conference on Complex Networks and their Applications (2019) (Himmel et al. 2019). This full version considers more optimization criteria, provides missing proofs, and presents extended experimental results. *Correspondence: [email protected] Anne-Sophie Himmel is supported by the DFG, project FPTinP (NI 369/16). Technische Universität Berlin, Faculty IV, Algorithmics and Computational Complexity, Berlin, Germany
Abstract 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. Keywords: Temporal networks, Temporal paths, Shortest path computation, Waiting policies, Infectious disease spreading
Introduction Computing shortest paths in networks is arguably among the most important graph algorithms. It is relevant in numerous application contexts and used as a subroutine in a highly diverse set of applications. While the respective problem has been studied for static graphs for decades, over the last years there has been an intensified interest in studying shortest path computations in temporal graphs—graphs where the vertex set remains static, but the arc set may change over time (in discrete time steps). © The Author(s). 2020 Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material i
Data Loading...
