DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2025.41

Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs

Authors: Ashish Saxena and Kaushik Mondal

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

We study the exploration problem by mobile agents in Connectivity Time dynamic graphs. The Connectivity Time model was introduced by Michail et al. [JPDC 2014] and is arguably one of the weakest dynamic graph connectivity models. We prove that exploration is impossible in such graphs using ((n-1)(n-2))/2 mobile agents starting from an arbitrary initial configuration, even when agents have full knowledge of system parameters, global communication, full visibility, and infinite memory. We then present an exploration algorithm that uses ((n-1)(n-2))/2 + 1 agents equipped with global communication, 1-hop visibility and O(log n) memory.

Cite as

Ashish Saxena and Kaushik Mondal. Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 41:1-41:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{saxena_et_al:LIPIcs.DISC.2025.41,
  author =	{Saxena, Ashish and Mondal, Kaushik},
  title =	{{Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{41:1--41:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.41},
  URN =		{urn:nbn:de:0030-drops-248585},
  doi =		{10.4230/LIPIcs.DISC.2025.41},
  annote =	{Keywords: Mobile agents, Anonymous graphs, Exploration, Dynamic graphs, Deterministic algorithm}
}

Search Results

Documents authored by Saxena, Ashish

Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message