Bounds on the cover time of parallel rotor walks
The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node successively propagates walkers visiting it along its outgoing arcs in round-robin fashion, according to a fixed ordering. We consider the cover time of such a system, i.e., the number of steps after which each node has been visited by at least one walk, regardless of the initialization of the walks. We show that for any graph with m edges and diameter D , this cover time is at most Θ(mD/logk) and at least Θ(mD/k), which corresponds to a speedup of between Θ(logk) and Θ(k) with respect to the cover time of a single walk.
Dariusz Dereniowski, Adrian Kosowski, Dominik Pająk, Przemysław Uznański. (2016). Bounds on the cover time of parallel rotor walks, 82(5), 802-816. https://doi.org/10.1016/j.jcss.2016.01.004
wyświetlono 14 razy