Wyszukiwarka
Abstrakt
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.
Cytowania
-
7
CrossRef
-
0
Web of Science
-
7
Scopus
Autorzy (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
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.jcss.2016.01.004
- Licencja
- Copyright (2016 Elsevier Inc)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
nr 82,
wydanie 5,
strony 802 - 816,
ISSN: 0022-0000 - Język:
- angielski
- Rok wydania:
- 2016
- Opis bibliograficzny:
- 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:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.jcss.2016.01.004
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 130 razy
Publikacje, które mogą cię zainteresować
Bounds on the Cover Time of Parallel Rotor Walks
- D. Dereniowski,
- A. Kosowski,
- D. Pająk
- + 1 autorów
Rendezvous of Heterogeneous Mobile Agents in Edge-Weighted Networks
- D. Dereniowski,
- Ł. Kuszner,
- A. Kosowski
- + 1 autorów
Rendezvous of heterogeneous mobile agents in edge-weighted networks
- D. Dereniowski,
- R. Klasing,
- A. Kosowski
- + 1 autorów