Bounds on the cover time of parallel rotor walks - Publikacja - MOST Wiedzy

Wyszukiwarka

Bounds on the cover time of parallel rotor walks

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/log⁡k) and at least Θ(mD/k), which corresponds to a speedup of between Θ(log⁡k) and Θ(k) with respect to the cover time of a single walk.

Cytowania

  • 3

    CrossRef

  • 1

    Web of Science

  • 1

    Scopus

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

wyświetlono 10 razy

Publikacje, które mogą cię zainteresować

Meta Tagi