The Cover Time of Deterministic Random Walks
作者： Tobias Friedrich , Thomas Sauerwald
DOI: 10.1007/978-3-642-14031-0_16
关键词: Random graph 、 Heterogeneous random walk in one dimension 、 Combinatorics 、 Random function 、 Random field 、 Random walk 、 Random regular graph 、 Quantum walk 、 Discrete mathematics 、 Mathematics 、 Loop-erased random walk
摘要: The rotor router model is a popular deterministic analogue of random walk on graph. Instead moving to neighbor, the neighbors are served in fixed order. We examine how fast this "deterministic walk" covers all vertices (or edges). present general techniques derive upper bounds for vertex and edge cover time matching lower several important graph classes. Depending topology, can be asymptotically faster, slower or equally compared classical walk.
springer.com
core.ac.uk
mpg.de
sci-hub.st 参考文章(53)
Alan Frieze, Colin Cooper, The cover time of random geometric graphs symposium on discrete algorithms. pp. 48- 57 ,(2009) , 10.5555/1496770.1496776
Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald, Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness Automata, Languages and Programming. pp. 366- 377 ,(2009) , 10.1007/978-3-642-02927-1_31
Chen Avin, Michal Koucký, Zvi Lotker, How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs) international colloquium on automata languages and programming. pp. 121- 132 ,(2008) , 10.1007/978-3-540-70575-8_11
Y. Rabani, A. Sinclair, R. Wanka, Local divergence of Markov chains and the analysis of iterative load-balancing schemes foundations of computer science. pp. 694- 703 ,(1998) , 10.1109/SFCS.1998.743520
Joshua Cooper, Benjamin Doerr, Joel Spencer, Gábor Tardos, Deterministic random walks on the integers The Journal of Combinatorics. ,vol. 28, pp. 2072- 2090 ,(2007) , 10.1016/J.EJC.2007.04.018
Persi Diaconis, Laurent Saloff-Coste, COMPARISON THEOREMS FOR REVERSIBLE MARKOV CHAINS Annals of Applied Probability. ,vol. 3, pp. 696- 730 ,(1993) , 10.1214/AOAP/1177005359
Greg Barnes, Uriel Feige, Short Random Walks on Graphs SIAM Journal on Discrete Mathematics. ,vol. 9, pp. 19- 28 ,(1996) , 10.1137/S0895480194264988
Alan Frieze, Colin Cooper, The cover time of the giant component of a random graph Random Structures and Algorithms. ,vol. 32, pp. 401- 439 ,(2008) , 10.1002/RSA.V32:4
Ioana Dumitriu, Prasad Tetali, Peter Winkler, On Playing Golf with Two Balls SIAM Journal on Discrete Mathematics. ,vol. 16, pp. 604- 615 ,(2003) , 10.1137/S0895480102408341
Colin Cooper, Alan Frieze, The Cover Time of Random Regular Graphs SIAM Journal on Discrete Mathematics. ,vol. 18, pp. 728- 740 ,(2005) , 10.1137/S0895480103428478