A tight lower bound on the cover time for random walks on graphs
From MaRDI portal
Publication:4845080
DOI10.1002/rsa.3240060406zbMath0832.60016OpenAlexW2170807097MaRDI QIDQ4845080
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
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 (41)
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
This page was built for publication: A tight lower bound on the cover time for random walks on graphs
