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

DOI10.1002/rsa.3240060106zbMath0811.60060OpenAlexW4230376356MaRDI QIDQ4322474

Uriel Feige

Publication date: 19 April 1995

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

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

zbMATH Keywords

hitting timerandom walks on graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05)

Related Items (44)

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 ⋮ Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time ⋮ Memory Efficient Anonymous Graph Exploration ⋮ The Hitting Time of Multiple Random Walks ⋮ The cover time of the preferential attachment graph ⋮ The cover time of a biased random walk on a random cubic graph ⋮ The Weighted Coupon Collector’s Problem and Applications ⋮ Random walks on edge transitive graphs ⋮ Collecting coupons on trees, and the cover time of random walks ⋮ On the Cover Time of the Emerging Giant ⋮ A tight lower bound on the cover time for random walks on graphs ⋮ Continuous monitoring in the dynamic sensor field model ⋮ Reversible random walks on dynamic graphs ⋮ Stationary distribution and cover time of random walks on random digraphs ⋮ Guided sampling for large 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 ⋮ Random walks on graphs and Monte Carlo methods ⋮ 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 ⋮ Lollipop and Lariat Symmetric Functions ⋮ The hitting and cover times of Metropolis walks ⋮ Tight bounds for the cover time of multiple random walks ⋮ Sum rules for hitting times of Markov chains ⋮ Unnamed Item ⋮ Theory and Practice of Discrete Interacting Agents Models ⋮ Many Random Walks Are Faster Than One ⋮ Cover time in edge-uniform stochastically-evolving graphs ⋮ The maximum relaxation time of a random walk ⋮ The hitting and cover times of random walks on finite graphs using local degree information ⋮ Chromatic posets ⋮ 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 ⋮ Does adding more agents make a difference? A case study of cover time for the rotor-router ⋮ New Bounds for Edge-Cover by Random Walk ⋮ 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
• The electrical resistance of a graph captures its commute and cover times
• Collisions Among Random Walks on a Graph
• Maximum hitting time for random walks on graphs

This page was built for publication: A tight upper bound on the cover time for random walks on graphs