Exploration of dynamic networks: Tight bounds on the number of agents

摘要

We consider, for the first time, the exploration of dynamic graphs of arbitrary unknown topology. We study the number of agents necessary and sufficient to explore such graphs under the fully synchronous (Fsync) and the semi-synchronous (Ssync) activation schedulers. We prove that, under the minimal assumption on the dynamics, temporal connectivity, the number of agents sufficient to perform exploration depends on a parameter we call evanescence of the graph, and this number is tight. We then consider the stronger well-known assumption of 1-interval connectivity when the number of edges missing at each time is bounded. We provide tight bounds also in this setting, proving the existence of a difference between Fsync and Ssync, as well as between anonymous and non-anonymous agents.