Dominik Pajak: Speedup in Graph Exploration with Multiple Walkers

Multiple walks in graph move in parallel across the edges of an initially unknown graph without central control with the goal of visiting all the vertices. Cover time of a given exploration algorithm is simply the number of steps needed until all the vertices are visited at least once by some walker assuming the worst case initial configuration. Speedup is the ratio between the cover time for a single walk and for multiple walks. We will study the speedup of two algorithms: multiple random walks and multi-agent rotor-router. In the rotor-router each node maintains a pointer to one of its neighbors and sends the walkers that visit it to the neighbors in a round-robin fashion. It can be seen as a derandomized version of random walks because each node sends the same number of walkers in every direction. We will derive the speedup for some graph classes like grids, random graphs or trees as well as some general bounds.