A Technique for Lower Bounding the Cover Time
From MaRDI portal
Publication:3989014
DOI10.1137/0405007zbMath0743.60068MaRDI QIDQ3989014
Publication date: 28 June 1992
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/019c97e89307b3e08793cc21c797169674fdd2e1
stationary distribution; vertex transitive; expected hitting times; covering times of random walks on graphs
60G50: Sums of independent random variables; random walks
Related Items
A model of self‐avoiding random walks for searching complex networks, A tight lower bound on the cover time for random walks on graphs, Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time, Memory Efficient Anonymous Graph Exploration, Hitting times for random walks on tricyclic graphs, Cover times, blanket times, and majorizing measures, Tight bounds for the cover time of multiple random walks, Random walk covering of some special trees, The electrical resistance of a graph captures its commute and cover times, Exponential concentration of cover times, On an epidemic model on finite graphs, Does adding more agents make a difference? A case study of cover time for the rotor-router, Threshold limits for cover times
