Bounds on the cover time
From MaRDI portal
Publication:1823547
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)
Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50)
Related Items (24)
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