DROPS

Document

DOI: 10.4230/LIPIcs.SAND.2023.13

Restless Exploration of Periodic Temporal Graphs

Authors: Thomas Bellitto, Cyril Conchon-Kerjan, and Bruno Escoffier

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract

A temporal graph is a sequence of graphs, indexed by discrete time steps, with a fixed vertex set but with an edge set that is able to change over time. In the temporal graph exploration problem, an agent wants to visit all the vertices of a given temporal graph. In the classical model, at each time step the agent can either stay where they are, or move along one edge. In this work we add a constraint called restlessness that forces the agent to move along one edge at each time step. We mainly focus on (infinite) periodical temporal graphs. We show that if the period is 2 one can decide in polynomial time whether exploring the whole graph is possible or not, while this problem turns out to be NP-hard for any period p ≥ 3. We also show some time bounds on the explorations of such graphs when the exploration is possible.

Cite as

Thomas Bellitto, Cyril Conchon-Kerjan, and Bruno Escoffier. Restless Exploration of Periodic Temporal Graphs. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bellitto_et_al:LIPIcs.SAND.2023.13,
  author =	{Bellitto, Thomas and Conchon-Kerjan, Cyril and Escoffier, Bruno},
  title =	{{Restless Exploration of Periodic Temporal Graphs}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{13:1--13:15},
  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/entities/document/10.4230/LIPIcs.SAND.2023.13},
  URN =		{urn:nbn:de:0030-drops-179497},
  doi =		{10.4230/LIPIcs.SAND.2023.13},
  annote =	{Keywords: Temporal graphs, Graph exploration, NP-completeness}
}

Search Results

Documents authored by Conchon-Kerjan, Cyril

Restless Exploration of Periodic Temporal Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message