Abstract

The most natural deterministic analogue of the random walk in graphs is a process in which walkers are propagated by each node to its neighbours in a round-robin fashion. Such process, called the rotor-router has applications for example in load balancing and rumor spreading. In this talk we will study the speed-up of k-agent rotor-router system with respect to the cover time of a single walk.

We will completely resolve the question of the possible range of speed-ups, showing that its value is between Θ(log k) and Θ(k), for any graph. Both of these bounds are tight. Thus, the proven range of speed-up for the rotor-router corresponds precisely to the conjectured range of speed-up for the random walk. We will also study the speed-up on various graph classes like expanders and multidimensional grids.

Joint work with D. Dereniowski, R. Klasing, A. Kosowski, T. Sauerwald, P. Uznanski.