Showing 2019Show all
3 papers · 1 filter
cs.CC2019
Multistage Graph Problems on a Global Budget
Klaus Heeger, Anne-Sophie Himmel, Frank Kammer +3
Time-evolving or temporal graphs gain more and more popularity when studying the behavior of complex networks. In this context, the multistage view on computational problems is amo…
cs.DM2019
The Computational Complexity of Finding Temporal Paths under Waiting Time Constraints
Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter +1
Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, grap…
cs.DS2019
Efficient Computation of Optimal Temporal Walks under Waiting-Time Constraints
Anne-Sophie Himmel, Matthias Bentert, André Nichterlein +1
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 ve…