License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAND.2023.4
URN: urn:nbn:de:0030-drops-179402
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17940/
Brunelli, Filippo ;
Viennot, Laurent
Computing Temporal Reachability Under Waiting-Time Constraints in Linear Time
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.
BibTeX - Entry
@InProceedings{brunelli_et_al:LIPIcs.SAND.2023.4,
author = {Brunelli, Filippo and Viennot, Laurent},
title = {{Computing Temporal Reachability Under Waiting-Time Constraints in Linear Time}},
booktitle = {2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
pages = {4:1--4:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-275-4},
ISSN = {1868-8969},
year = {2023},
volume = {257},
editor = {Doty, David and Spirakis, Paul},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17940},
URN = {urn:nbn:de:0030-drops-179402},
doi = {10.4230/LIPIcs.SAND.2023.4},
annote = {Keywords: temporal reachability, temporal graph, temporal path, temporal walk, waiting-time constraints, restless temporal walk, linear time}
}
|
Keywords: |
|
temporal reachability, temporal graph, temporal path, temporal walk, waiting-time constraints, restless temporal walk, linear time |
|
Collection: |
|
2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
12.06.2023 |
