DROPS

Document

Brief Announcement

DOI: 10.4230/LIPIcs.SAND.2026.22

Brief Announcement: Time-Travel Planning with Tenet Turnstiles

Authors: Thibaut Blanc, Quentin Bramas, Jean-Romain Luttringer, and Sébastien Tixeuil

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Abstract

We study routing in dynamic graphs when an agent may use backward time travel (BTT) devices. Minimizing delay (arrival time minus departure time) is the primary objective; the number of time inversions is the secondary cost. Building on the framework of Bramas et al., we introduce two space-time online settings - ST-online-easy and ST-online-hard - and analyze the Tenet model, where BTT is performed by entering a turnstile that reverses the direction of time flow. We obtain a polynomial-time offline algorithm, tight competitive ratios for the T-online and S-online settings, a tight quadratic competitive ratio for ST-online-easy, and we prove that no finite competitive ratio exists for ST-online-hard.

Cite as

Thibaut Blanc, Quentin Bramas, Jean-Romain Luttringer, and Sébastien Tixeuil. Brief Announcement: Time-Travel Planning with Tenet Turnstiles. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 22:1-22:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{blanc_et_al:LIPIcs.SAND.2026.22,
  author =	{Blanc, Thibaut and Bramas, Quentin and Luttringer, Jean-Romain and Tixeuil, S\'{e}bastien},
  title =	{{Brief Announcement: Time-Travel Planning with Tenet Turnstiles}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{22:1--22:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.22},
  URN =		{urn:nbn:de:0030-drops-262566},
  doi =		{10.4230/LIPIcs.SAND.2026.22},
  annote =	{Keywords: dynamic graphs, time travel, online algorithms}
}

Document

DOI: 10.4230/LIPIcs.SAND.2024.7

Online Space-Time Travel Planning in Dynamic Graphs

Authors: Quentin Bramas, Jean-Romain Luttringer, and Sébastien Tixeuil

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract

We study the problem of traveling in an unknown dynamic graph, to reach a destination with minimum latency. At each step of the execution, an agent can decide to move to a neighboring node if an edge exists at this time instant, wait at the current node in the hope that other links will appear in the future, or move backward in time using an expensive time travel device. A travel that makes use of backward time travel is called a space-time travel. Our aim is to arrive at the destination with zero delay, which always requires the use of backward time travel if no path exists to the destination during the first time instant. Finding an optimal space-time travel is polynomial when the agent knows the entire dynamic graph (including the future edges), even with additional constraints. However, we consider in this paper that the agent discovers the dynamic graph while it is exploring it, in an online manner. In this paper, we propose two models that define how an agent learns new knowledge about the dynamic graph during the execution of its protocol: the T-online model, where the agent reaching time t learns about the entire past of the network until t (even nodes not yet visited), and the S-online model, where the agent learns about the past and future about the current node he is located at. We present an algorithm with an optimal competitive ratio of 2 for the T-online model. In the S-online model, we prove a lower bound of 2/3n-7/4 and an upper bound of 2n-3 on the optimal competitive ratio when the cost function is linear.

Cite as

Quentin Bramas, Jean-Romain Luttringer, and Sébastien Tixeuil. Online Space-Time Travel Planning in Dynamic Graphs. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.SAND.2024.7,
  author =	{Bramas, Quentin and Luttringer, Jean-Romain and Tixeuil, S\'{e}bastien},
  title =	{{Online Space-Time Travel Planning in Dynamic Graphs}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.7},
  URN =		{urn:nbn:de:0030-drops-198854},
  doi =		{10.4230/LIPIcs.SAND.2024.7},
  annote =	{Keywords: Dynamic graphs, online algorithm, space-time travel, treasure hunt}
}

Search Results

Documents authored by Luttringer, Jean-Romain

Brief Announcement: Time-Travel Planning with Tenet Turnstiles

Abstract

Cite as

Online Space-Time Travel Planning in Dynamic Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message