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.