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)O(D), using a team of agents of polynomial size k=Dn1+ϵ0ϵ>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.