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.2022.17
URN: urn:nbn:de:0030-drops-159598
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15959/
Go to the corresponding LIPIcs Volume Portal

Füchsle, Eugen ; Molter, Hendrik ; Niedermeier, Rolf ; Renken, Malte

Temporal Connectivity: Coping with Foreseen and Unforeseen Delays

pdf-format:
LIPIcs-SAND-2022-17.pdf (0.8 MB)

Abstract

Consider planning a trip in a train network. In contrast to, say, a road network, the edges are temporal, i.e., they are only available at certain times. Another important difficulty is that trains, unfortunately, sometimes get delayed. This is especially bad if it causes one to miss subsequent trains. The best way to prepare against this is to have a connection that is robust to some number of (small) delays. An important factor in determining the robustness of a connection is how far in advance delays are announced. We give polynomial-time algorithms for the two extreme cases: delays known before departure and delays occurring without prior warning (the latter leading to a two-player game scenario). Interestingly, in the latter case, we show that the problem becomes PSPACE-complete if the itinerary is demanded to be a path.

BibTeX - Entry

@InProceedings{fuchsle_et_al:LIPIcs.SAND.2022.17,
  author =	{F\"{u}chsle, Eugen and Molter, Hendrik and Niedermeier, Rolf and Renken, Malte},
  title =	{{Temporal Connectivity: Coping with Foreseen and Unforeseen Delays}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15959},
  URN =		{urn:nbn:de:0030-drops-159598},
  doi =		{10.4230/LIPIcs.SAND.2022.17},
  annote =	{Keywords: Paths and walks in temporal graphs, static expansions of temporal graphs, two-player games, flow computations, dynamic programming, PSPACE-completeness}
}

Keywords: Paths and walks in temporal graphs, static expansions of temporal graphs, two-player games, flow computations, dynamic programming, PSPACE-completeness
Collection: 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Issue Date: 2022
Date of publication: 29.04.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI