Bounds on the Cover Time of Parallel Rotor Walks

Dariusz Dereniowski; Adrian Kosowski; Dominik Pająk; Przemysław Uznański

doi:10.1016/j.jcss.2016.01.004

Bounds on the Cover Time of Parallel Rotor Walks

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)).

Citations

7

CrossRef
0

Web of Science
7

Scopus

Authors (4)

Dariusz Dereniowski prof. dr hab. inż.
Adrian Kosowski
- Inria Bordeaux Sud-Ouest; Inria Paris Rocquencourt – LIAFA CEPAGE Project, LaBRI; GANG Project
Dominik Pająk
- Inria Bordeaux Sud-Ouest CEPAGE Project, LaBRI
Przemysław Uznański
- CNRS and Aix-Marseille Université LIF

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:: Conference activity
Type:: publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Title of issue:: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) : Leibniz International Proceedings in Informatics (LIPIcs) strony 263 - 275
Language:: English
Publication year:: 2014
Bibliographic description:: Dereniowski D., Kosowski A., Pająk ., Uznański P.: Bounds on the Cover Time of Parallel Rotor Walks// 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) : Leibniz International Proceedings in Informatics (LIPIcs)/ ed. Ernst W. Mayr and Natacha Portier Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2014, s.263-275
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.jcss.2016.01.004
Verified by:: Gdańsk University of Technology