Geodesic
The cover time of deterministic random walks
The electronic journal of combinatorics, Tome 17 (2010)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The rotor router model is a popular deterministic analogue of a random walk on a graph. Instead of moving to a random neighbor, the neighbors are served in a fixed order. We examine how quickly this "deterministic random walk" covers all vertices (or all edges). We present general techniques to derive upper bounds for the vertex and edge cover time and derive matching lower bounds for several important graph classes. Depending on the topology, the deterministic random walk can be asymptotically faster, slower or equally fast as the classic random walk. We also examine the short term behavior of deterministic random walks, that is, the time to visit a fixed small number of vertices or edges.
DOI : 10.37236/439
Classification : 05C81 
@article{10_37236_439,
     author = {Tobias Friedrich and Thomas Sauerwald},
     title = {The cover time of deterministic random walks},
     journal = {The electronic journal of combinatorics},
     year = {2010},
     volume = {17},
     doi = {10.37236/439},
     zbl = {1201.05084},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/439/}
}
TY  - JOUR
AU  - Tobias Friedrich
AU  - Thomas Sauerwald
TI  - The cover time of deterministic random walks
JO  - The electronic journal of combinatorics
PY  - 2010
VL  - 17
UR  - http://geodesic.mathdoc.fr/articles/10.37236/439/
DO  - 10.37236/439
ID  - 10_37236_439
ER  - 
%0 Journal Article
%A Tobias Friedrich
%A Thomas Sauerwald
%T The cover time of deterministic random walks
%J The electronic journal of combinatorics
%D 2010
%V 17
%U http://geodesic.mathdoc.fr/articles/10.37236/439/
%R 10.37236/439
%F 10_37236_439
Tobias Friedrich; Thomas Sauerwald. The cover time of deterministic random walks. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/439

Cité par Sources :