Does Adding More Agents Make A Difference? A Case Study Of Cover Time For The Rotor-Router

We study the cover time of multiple walks in a graph following the rotor-router mechanism. This mechanism can be seen as a derandomization of multiple random walks, in which agents are propagated by nodes to neighbors in round-robin fashion. We provide a framework for analyzing parallel rotor-router walks, building on the relation of the model to a continuous diffusion process. We use and extend this approach to the determine the asymptotic value of the considered cover time for degree-restricted expanders, random graphs, constant-dimensional tori, and hypercubes. (C) 2019 Elsevier Inc. All rights reserved.