Fast collaborative graph exploration

We study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. We ask how many time steps are required to complete exploration, i. e. , to make sure that every vertex has been visited by some agent. As our main result, we provide the first strategy which performs exploration of a graph with n vertices at a distance of at most D from r in time O ( D ), using a team of agents of polynomial size k = D n 1 + ϵ < n 2 + ϵ, for any ϵ > 0. Our strategy works in the local communication model, in which agents can only exchange information when located at a vertex, without knowledge of global parameters such as n or D. We also obtain almost-tight bounds on the asymptotic relation between exploration time and team size, for large k, in both the local and the global communication model.

Authors

• Dariusz Dereniowski
• Yann Disser
• Adrian Kosowski
• Dominik Pająk
• Przemysław Uznański

Keywords

No keywords are indexed for this paper.