Bounds on the cover time

DOI10.1007/BF01048273zbMath0681.60063MaRDI QIDQ1823547

Anna R. Karlin, Andrei Z. Broder

Publication date: 1989

Published in: Journal of Theoretical Probability (Search for Journal in Brave)

zbMATH Keywords

upper and lower boundsmatrixrandom walks on graphscover timeseigenvalues of transition

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50)

Related Items

Analytical results for the distribution of cover times of random walks on random regular graphs ⋮ On the cover time and mixing time of random geometric graphs ⋮ On the mean and variance of cover times for random walks on graphs ⋮ The Hitting Time of Multiple Random Walks ⋮ Random walks and the effective resistance sum rules ⋮ Lower bounds on partial sums of expected hitting times ⋮ The electrical resistance of a graph captures its commute and cover times ⋮ Deconstructing 1-Local Expanders ⋮ On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting? ⋮ Markov chains on hypercubes: Spectral representations and several majorization relations ⋮ Bounding robustness in complex networks under topological changes through majorization techniques ⋮ Cover times, blanket times, and majorizing measures ⋮ On partial sums of hitting times ⋮ Graph Clustering using Effective Resistance ⋮ On the time to traverse all edges of a graph ⋮ Markov incremental constructions ⋮ Hitting times for random walks on vertex-transitive graphs ⋮ Greedy Random Walk ⋮ Laplace eigenvalues of graphs---a survey ⋮ Tight bounds for the cover time of multiple random walks ⋮ On certain connectivity properties of the internet topology ⋮ Sum rules for hitting times of Markov chains ⋮ Many Random Walks Are Faster Than One ⋮ Random Accessibility as a Parallelism to Reliability Studies on Simple Graphs

Cites Work

• Minimization algorithms and random walk on the d-cube
• Eigenvalues and expanders
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Bounds for eigenvalues of certain stochastic matrices
• On the cover time of random walks on graphs
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• On the time taken by random walks on finite groups to visit every state
• Some Extremal Markov Chains
• Inequalities: theory of majorization and its applications

This page was built for publication: Bounds on the cover time