DROPS

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

Search Results

Documents authored by Ayoubi, Kamran

Restless Exploration and Token Dissemination in Vertex-Permuted Temporal Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message