Dereniowski, Dariusz ;
Kosowski, Adrian ;
Pajak, Dominik ;
Uznanski, Przemyslaw
Bounds on the Cover Time of Parallel Rotor Walks
Abstract
The rotorrouter 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 roundrobin 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 nnode 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)).
BibTeX  Entry
@InProceedings{dereniowski_et_al:LIPIcs:2014:4463,
author = {Dariusz Dereniowski and Adrian Kosowski and Dominik Pajak and Przemyslaw Uznanski},
title = {{Bounds on the Cover Time of Parallel Rotor Walks}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {263275},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897651},
ISSN = {18688969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4463},
URN = {urn:nbn:de:0030drops44637},
doi = {10.4230/LIPIcs.STACS.2014.263},
annote = {Keywords: Distributed graph exploration, RotorRouter, Collaborative robots, Parallel random walks, Derandomization}
}
05.03.2014
Keywords: 

Distributed graph exploration, RotorRouter, Collaborative robots, Parallel random walks, Derandomization 
Seminar: 

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Issue date: 

2014 
Date of publication: 

05.03.2014 