2 Search Results for "Conchon-Kerjan, Cyril"

Document
DOI: 10.4230/LIPIcs.SAND.2025.12
Restless Exploration and Token Dissemination in Vertex-Permuted Temporal Graphs

Authors: Kamran Ayoubi and Lata Narayanan

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
In the temporal graph exploration problem, an agent wishes to visit all the vertices of a temporal graph, moving at most one edge in every time step. In restless exploration, the agent is required to move in every step, and cannot wait at a vertex. We study the problem of restless exploration in vertex-permuted graphs, which are a class of temporal graphs in which the topology of the graph stays the same in every time step. In other words, in a vertex permuted temporal graph, in every step i, the graph G_i is isomorphic to the same base graph G. We give a precise characterization of graphs G such that restless exploration is possible in every vertex-permuted graph with base graph G. Our technique is based on an a characterization of networks in which there is an online distributed algorithm for restless token dissemination. Finally we describe some families of graphs in which restless exploration is always possible, and some in which it is not.
Cite as

Kamran Ayoubi and Lata Narayanan. Restless Exploration and Token Dissemination in Vertex-Permuted Temporal Graphs. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ayoubi_et_al:LIPIcs.SAND.2025.12,
  author =	{Ayoubi, Kamran and Narayanan, Lata},
  title =	{{Restless Exploration and Token Dissemination in Vertex-Permuted Temporal Graphs}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.12},
  URN =		{urn:nbn:de:0030-drops-230658},
  doi =		{10.4230/LIPIcs.SAND.2025.12},
  annote =	{Keywords: Temporal graphs, Vertex permuted graphs, Restless exploration, Periodic graphs, Token dissemination}
}
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}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2023

  • Refine by Author
  • 1 Ayoubi, Kamran
  • 1 Bellitto, Thomas
  • 1 Conchon-Kerjan, Cyril
  • 1 Escoffier, Bruno
  • 1 Narayanan, Lata

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Theory of computation
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 2 Temporal graphs
  • 1 Graph exploration
  • 1 NP-completeness
  • 1 Periodic graphs
  • 1 Restless exploration
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact