Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router. - Archive ouverte HAL Access content directly
Journal Articles Journal of Computer and System Sciences Year : 2019

Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router.

(1) , (2)
1
2
Adrian Kosowski
  • Function : Author
  • PersonId : 907513
Dominik Pajak
  • Function : Author
  • PersonId : 930535

Abstract

We consider the problem of graph exploration by a team of $k$ agents, which follow the so-called rotor router mechanism. Agents move in synchronous rounds, and each node successively propagates agents which visit it along its outgoing arcs in round-robin fashion. It has recently been established by Dereniowski et al.\ (STACS 2014) that the rotor-router cover time of a graph $G$, i.e., the number of steps required by the team of agents to visit all of the nodes of $G$, satisfies a lower bound of $\Omega(mD/k)$ and an upper bound of $O(mD/\log k)$ for any graph with $m$ edges and diameter $D$. In this paper, we consider the question of how the cover time of the rotor-router depends on $k$ for many important graph classes. We determine the precise asymptotic value of the rotor-router cover time for all values of $k$ for degree-restricted expanders, random graphs, and constant-dimensional tori. For hypercubes, we also resolve the question precisely, except for values of $k$ much larger than $n$. Our results can be compared to those obtained by Elsässer and Sauerwald (ICALP 2009) in an analogous study of the cover time of $k$ independent parallel random walks in a graph; for the rotor-router, we obtain tight bounds in a slightly broader spectrum of cases. Our proofs take advantage of a relation which we develop, linking the cover time of the rotor-router to the mixing time of the random walk and the local divergence of a discrete diffusion process on the considered graph.
Fichier principal
Vignette du fichier
rrcases.pdf (210.46 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00950743 , version 1 (22-02-2014)
hal-00950743 , version 2 (25-03-2014)
hal-00950743 , version 3 (25-03-2014)

Identifiers

Cite

Adrian Kosowski, Dominik Pajak. Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router.. Journal of Computer and System Sciences, 2019, 106, pp.80-93. ⟨10.1016/j.jcss.2019.07.001⟩. ⟨hal-00950743v3⟩
606 View
840 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More