Document Open Access Logo

Computing Temporal Reachability Under Waiting-Time Constraints in Linear Time

Authors Filippo Brunelli, Laurent Viennot

PDF
Thumbnail PDF

File

LIPIcs.SAND.2023.4.pdf
  • Filesize: 0.67 MB
  • 11 pages

Document Identifiers

Author Details

Filippo Brunelli
  • Université Paris Cité, Inria, CNRS, IRIF, Paris, France
Laurent Viennot
  • Université Paris Cité, Inria, CNRS, IRIF, Paris, France

Funding

This work was supported by the French National Research Agency (ANR) through project Tempogral with reference number ANR-22-CE48-0001.

Cite AsGet BibTex

Filippo Brunelli and Laurent Viennot. Computing Temporal Reachability Under Waiting-Time Constraints in Linear Time. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 4:1-4:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SAND.2023.4

Abstract

This paper proposes a simple algorithm for computing single-source reachability in a temporal graph under waiting-time constraints, that is when waiting at each node is bounded by some time constraints. Given a space-time representation of a temporal graph, and a source node, the algorithm computes in linear-time which nodes and temporal edges are reachable through a constrained temporal walk from the source.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
  • Mathematics of computing → Graph algorithms
Keywords
  • temporal reachability
  • temporal graph
  • temporal path
  • temporal walk
  • waiting-time constraints
  • restless temporal walk
  • linear time

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Matthias Bentert, Anne-Sophie Himmel, André Nichterlein, and Rolf Niedermeier. Efficient computation of optimal temporal walks under waiting-time constraints. Appl. Netw. Sci., 5(1):73, 2020. Google Scholar
  2. Kenneth A. Berman. Vulnerability of scheduled networks and a generalization of menger’s theorem. Networks, 28(3):125-134, 1996. Google Scholar
  3. Gerth Stølting Brodal and Riko Jacob. Time-dependent networks as models to achieve fast exact time-table queries. Electron. Notes Theor. Comput. Sci., 92:3-15, 2004. Google Scholar
  4. Filippo Brunelli and Laurent Viennot. Minimum-cost temporal walks under waiting-time constraints in linear time. CoRR, abs/2211.12136, 2022. URL: https://doi.org/10.48550/arXiv.2211.12136.
  5. Richard T. Bumby. A problem with telephones. SIAM. J. on Algebraic and Discrete Methods, 2(1):13-18, 1981. Google Scholar
  6. Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. IJPEDS, 27(5):387-408, 2012. Google Scholar
  7. Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche. Finding temporal paths under waiting time constraints. Algorithmica, 83(9):2754-2802, 2021. Google Scholar
  8. Kenneth L. Cooke and Eric Halsey. The shortest route through a network with time-dependent internodal transit times. Journal of Mathematical Analysis and Applications, 14(3):493-498, 1966. Google Scholar
  9. Pierluigi Crescenzi, Clémence Magnien, and Andrea Marino. Approximating the temporal neighbourhood function of large temporal graphs. Algorithms, 12(10):211, 2019. Google Scholar
  10. Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Intriguingly Simple and Fast Transit Routing. In Experimental Algorithms, Lecture Notes in Computer Science, pages 43-54. Springer, 2013. Google Scholar
  11. Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Connection scan algorithm. ACM Journal of Experimental Algorithmics, 23:1.7:1-1.7:56, 2018. Google Scholar
  12. Arthur B. Kahn. Topological sorting of large networks. Commun. ACM, 5(11):558-562, 1962. Google Scholar
  13. Matthieu Latapy, Tiphaine Viard, and Clémence Magnien. Stream graphs and link streams for the modeling of interactions over time. Social Netw. Analys. Mining, 8(1):61:1-61:29, 2018. Google Scholar
  14. Othon Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics, 12(4):239-280, 2016. Google Scholar
  15. Matthias Müller-Hannemann, Frank Schulz, Dorothea Wagner, and Christos D. Zaroliagis. Timetable information: Models and algorithms. In ATMOS, volume 4359 of Lecture Notes in Computer Science, pages 67-90. Springer, 2004. Google Scholar
  16. Karl Nachtigall. Time depending shortest-path problems with applications to railway networks. European Journal of Operational Research, 83(1):154-166, 1995. Google Scholar
  17. Stefano Pallottino and Maria Grazia Scutellà. Shortest path algorithms in transportation models: classical and innovative aspects. Technical Report TR-97-06, University of Pisa, 1997. Google Scholar
  18. Stefano Pallottino and Maria Grazia Scutellà. Equilibrium and Advanced Transportation Modelling, chapter Shortest path algorithms in transportation models: classical and innovative aspects, pages 245-281. Kluwer Academic Publishers, 1998. Google Scholar
  19. Frank Schulz, Dorothea Wagner, and Karsten Weihe. Dijkstra’s algorithm on-line: An empirical case study from public railroad transport. ACM J. Exp. Algorithmics, 5:12, 2000. Google Scholar
  20. Huanhuan Wu, James Cheng, Silu Huang, Yiping Ke, Yi Lu, and Yanyan Xu. Path Problems in Temporal Graphs. VLDB Endowment, 7(9):721-732, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact