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}
}

Search Results

Documents authored by Blanc, Thibaut

Brief Announcement: Time-Travel Planning with Tenet Turnstiles

Abstract

Cite as

Thanks for your feedback!

Could not send message