2026-07-25T00:37:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4463 2024-03-06T10:35:04Z ddc:004 open_access

Bounds on the Cover Time of Parallel Rotor Walks Dereniowski, Dariusz Kosowski, Adrian Pajak, Dominik Uznanski, Przemyslaw Distributed graph exploration Rotor-Router Collaborative robots Parallel random walks Derandomization 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 maintains a cyclic ordering of its outgoing arcs, and successively propagates walkers which visit it along its outgoing arcs in round-robin fashion, according to the 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 starting locations of the walks. In the case of k=1, [Yanovski et al., 2003] and [Bampas et al., 2009] showed that a single walk achieves a cover time of exactly Theta(mD) for any n-node graph with m edges and diameter D, and that the walker eventually stabilizes to a traversal of an Eulerian circuit on the set of all directed edges of the graph. For k>1 parallel walks, no similar structural behaviour can be observed. In this work we provide tight bounds on the cover time of k parallel rotor walks in a graph. We show that this cover time is at most (mD/log(k)) and at least Theta(mD/k) for any graph, which corresponds to a speedup of between Theta(log(k)) and Theta(k) with respect to the cover time of a single walk. Both of these extremal values of speedup are achieved for some graph classes. Our results hold for up to a polynomially large number of walks, k=O(poly(n)). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dariusz Dereniowski and Adrian Kosowski and Dominik Pajak and Przemyslaw Uznanski 2014 Is Part Of LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2014.263 urn:nbn:de:0030-drops-44637 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.263 eng https://creativecommons.org/licenses/by/3.0/legalcode