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

DOI10.1002/rsa.3240060406zbMath0832.60016OpenAlexW2170807097MaRDI QIDQ4845080

Uriel Feige

Publication date: 20 February 1996

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240060406

zbMATH Keywords

random walksgraphs

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05)

Related Items

Random walks on graphs with interval weights and precise marginals, 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 mixing times for stratified walks on thed-cube, Memory Efficient Anonymous Graph Exploration, The cover time of the preferential attachment graph, Exact mixing times for random walks on trees, The cover time of a biased random walk on a random cubic graph, The Weighted Coupon Collector’s Problem and Applications, Collecting coupons on trees, and the cover time of random walks, On the Cover Time of the Emerging Giant, Multiple random walks on graphs: mixing few to cover many, Stationary distribution and cover time of random walks on random digraphs, Linear cover time is exponentially unlikely, A collection of results concerning electric resistance and simple random walk on distance-regular graphs, Cover times, blanket times, and majorizing measures, A spectral characterization for concentration of the cover time, Stationary distribution and cover time of sparse directed configuration models, Cover time of a random graph with given degree sequence, On the cover time of \(\lambda\)-biased walk on supercritical Galton-Watson trees, The Evolution of the Cover Time, The cover time of random geometric graphs, The Cover Time of Cartesian Product Graphs, PERFORMANCE ANALYSIS AND EVALUATION OF RANDOM WALK ALGORITHMS ON WIRELESS NETWORKS, A multiple random walks based self-stabilizingk-exclusion algorithm in ad hoc networks, The best mixing time for random walks on trees, Frogs on trees?, A model of self‐avoiding random walks for searching complex networks, Greedy Random Walk, The hitting and cover times of Metropolis walks, Tight bounds for the cover time of multiple random walks, Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time, Unnamed Item, Theory and Practice of Discrete Interacting Agents Models, Many Random Walks Are Faster Than One, The hitting and cover times of random walks on finite graphs using local degree information, Chung-Yau Invariants and Graphs with Symmetric Hitting Times, The cover time of deterministic random walks for general transition probabilities, How to Design a Linear Cover Time Random Walk on a Finite Graph, On the Cover Time of Dense Graphs, Cover time of a random graph with a degree sequence II: Allowing vertices of degree two

Cites Work

• Random walks and the effective resistance of networks
• Covering problems for Brownian motion on spheres
• The electrical resistance of a graph captures its commute and cover times
• On the cover time of random walks on graphs
• An introduction to covering problems for random walks on graphs
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• Collisions Among Random Walks on a Graph
• A Technique for Lower Bounding the Cover Time
• A tight upper bound on the cover time for random walks on graphs
• Extremal cover times for random walks on trees