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