A Technique for Lower Bounding the Cover Time

DOI10.1137/0405007MaRDI QIDQ3989014zbMATHOpenAlexFDO

Authors David Zuckerman

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

zbMATH Keywords

stationary distributionvertex transitiveexpected hitting timescovering times of random walks on graphs

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50)

Recommendations

• On the cover time of random walks on graphs
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• Bounds on the cover time
• A bound for the covering time of random walks on graphs
• Expected cover times of random walks on symmetric graphs

Cited in

(21)

• Cover times, blanket times, and majorizing measures
• The power of two choices for random walks
• Threshold limits for cover times
• Random walk covering of some special trees
• How to Design a Linear Cover Time Random Walk on a Finite Graph
• Does adding more agents make a difference? A case study of cover time for the rotor-router
• Tight bounds for the cover time of multiple random walks
• On an epidemic model on finite graphs
• The electrical resistance of a graph captures its commute and cover times
• Hitting times for random walks on tricyclic graphs
• Bounds on the cover time
• Memory Efficient Anonymous Graph Exploration
• A bound for the covering time of random walks on graphs
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• Random walks which prefer unvisited edges: exploring high girth even degree expanders in linear time
• A lower bound for the coverability problem in acyclic pushdown VAS
• Cover time and broadcast time
• \(O(n \log n)\) procedures for tightening cover inequalities
• A tight lower bound on the cover time for random walks on graphs
• A model of self-avoiding random walks for searching complex networks
• Exponential concentration of cover times

This page was built for publication: A Technique for Lower Bounding the Cover Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3989014)