Bounds on the cover time
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 479-487
- https://doi.org/10.1109/sfcs.1988.21964
Abstract
A particle that moves on a connected unidirected graph G with n vertices is considered. At each step the particle goes from the current vertex to one of its neighbors, chosen uniformly at random. The cover time is the first time when the particle has visited all the vertices in the graph, starting from a given vertex. Upper and lower bounds are presented that relate the expected cover time for a graph to the eigenvalues of the Markov chain that describes the above random walk. An interesting consequence is that regular expander graphs have expected cover time theta (n log n).Keywords
This publication has 9 references indexed in Scilit:
- Eigenvalues and graph bisection: An average-case analysisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- On the second eigenvalue of random regular graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Eigenvalues and expandersCombinatorica, 1986
- Minimization Algorithms and Random Walk on the $d$-CubeThe Annals of Probability, 1983
- On the time taken by random walks on finite groups to visit every stateProbability Theory and Related Fields, 1983
- Random walks on finite groups and rapidly mixing markov chainsPublished by Springer Nature ,1983
- Some Extremal Markov ChainsBell System Technical Journal, 1982
- Bounds for eigenvalues of certain stochastic matricesLinear Algebra and its Applications, 1981
- Random walks, universal traversal sequences, and the complexity of maze problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979