Bounds on the Cover Time of Parallel Rotor Walks

Authors Dariusz Dereniowski, Adrian Kosowski, Dominik Pajak, Przemyslaw Uznanski



PDF
Thumbnail PDF

File

LIPIcs.STACS.2014.263.pdf
  • Filesize: 0.69 MB
  • 13 pages

Document Identifiers

Author Details

Dariusz Dereniowski
Adrian Kosowski
Dominik Pajak
Przemyslaw Uznanski

Cite AsGet BibTex

Dariusz Dereniowski, Adrian Kosowski, Dominik Pajak, and Przemyslaw Uznanski. Bounds on the Cover Time of Parallel Rotor Walks. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 263-275, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.STACS.2014.263

Abstract

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)).
Keywords
  • Distributed graph exploration
  • Rotor-Router
  • Collaborative robots
  • Parallel random walks
  • Derandomization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail