2026-07-21T14:16:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24858 2026-02-09T07:42:02Z ddc:004 open_access

Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs Saxena, Ashish Mondal, Kaushik Mobile agents Anonymous graphs Exploration Dynamic graphs Deterministic algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ashish Saxena and Kaushik Mondal 2025 Is Part Of LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2025.41 urn:nbn:de:0030-drops-248585 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.41 eng https://creativecommons.org/licenses/by/4.0/legalcode