A tight upper bound on the cover time for random walks on graphs

1995/01/01 by Uriel Feige · 4 citations
Computer Science · #Optimization and Search Problems #Complexity and Algorithms in Graphs #Algorithms and Data Compression

paper · doi:10.1002/rsa.3240060106

openalex publication_date 1995/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21

Abstract

Abstract We prove that the expected time for a random walk to visit all n vertices of a connected graph is at most 4/27 n 3 + o ( n 3 ).

Citations

• Maximum hitting time for random walks on graphs

Cited by

• Cover times, blanket times, and majorizing measures
• New Bounds for Edge-Cover by Random Walk
• Mean first-passage time for random walks in general graphs with a deep trap
• Lollipop graph [wikipedia]