DROPS

Document

DOI: 10.4230/LIPIcs.SAND.2022.17

Temporal Connectivity: Coping with Foreseen and Unforeseen Delays

Authors: Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

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.

Cite as

Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken. Temporal Connectivity: Coping with Foreseen and Unforeseen Delays. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.SAND.2022.17},
  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}
}

Document

DOI: 10.4230/LIPIcs.STACS.2022.30

Delay-Robust Routes in Temporal Graphs

Authors: Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract

Most transportation networks are inherently temporal: Connections (e.g. flights, train runs) are only available at certain, scheduled times. When transporting passengers or commodities, this fact must be considered for the the planning of itineraries. This has already led to several well-studied algorithmic problems on temporal graphs. The difficulty of the described task is increased by the fact that connections are often unreliable - in particular, many modes of transportation suffer from occasional delays. If these delays cause subsequent connections to be missed, the consequences can be severe. Thus, it is a vital problem to design itineraries that are robust to (small) delays. We initiate the study of this problem from a parameterized complexity perspective by proving its NP-completeness as well as several hardness and tractability results for natural parameterizations.

Cite as

Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken. Delay-Robust Routes in Temporal Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fuchsle_et_al:LIPIcs.STACS.2022.30,
  author =	{F\"{u}chsle, Eugen and Molter, Hendrik and Niedermeier, Rolf and Renken, Malte},
  title =	{{Delay-Robust Routes in Temporal Graphs}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.30},
  URN =		{urn:nbn:de:0030-drops-158403},
  doi =		{10.4230/LIPIcs.STACS.2022.30},
  annote =	{Keywords: algorithms and complexity, parameterized complexity, time-varying networks, temporal paths, journeys}
}

Search Results

Documents authored by Füchsle, Eugen

Temporal Connectivity: Coping with Foreseen and Unforeseen Delays

Abstract

Cite as

Delay-Robust Routes in Temporal Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message