Search
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 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.
Citations
-
7
CrossRef
-
0
Web of Science
-
7
Scopus
Authors (4)
-
Adrian Kosowski
- Inria Paris and IRIF GANG Project
-
Dominik Pająk
- Faculty of Fundamental Problems of Technology, Wrocław University of Technology Department of Computer Science
-
Przemysław Uznański
- ETH Zürich Department of Computer Science
Cite as
Full text
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.jcss.2016.01.004
- License
- Copyright (2016 Elsevier Inc)
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
no. 82,
edition 5,
pages 802 - 816,
ISSN: 0022-0000 - Language:
- English
- Publication year:
- 2016
- Bibliographic description:
- Dereniowski D., Kosowski A., Pająk D., Uznański P.: Bounds on the cover time of parallel rotor walks// JOURNAL OF COMPUTER AND SYSTEM SCIENCES. -Vol. 82, iss. 5 (2016), s.802-816
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.jcss.2016.01.004
- Verified by:
- Gdańsk University of Technology
seen 133 times
Recommended for you
Bounds on the Cover Time of Parallel Rotor Walks
- D. Dereniowski,
- A. Kosowski,
- D. Pająk
- + 1 authors
Rendezvous of Heterogeneous Mobile Agents in Edge-Weighted Networks
- D. Dereniowski,
- Ł. Kuszner,
- A. Kosowski
- + 1 authors
Rendezvous of heterogeneous mobile agents in edge-weighted networks
- D. Dereniowski,
- R. Klasing,
- A. Kosowski
- + 1 authors