Tight bounds for the cover time of multiple random walks

DOI10.1016/j.tcs.2010.08.010zbMath1227.68030OpenAlexW2046919262MaRDI QIDQ541669

Thomas Sauerwald, Robert Elsässer

Publication date: 7 June 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.08.010

zbMATH Keywords

graphrandom walkparallelcover timespeed-up

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Random walks on graphs (05C81)

Related Items

Bounds on the cover time of parallel rotor walks ⋮ Coalescing Walks on Rotor-Router Systems ⋮ A discrete random walk on the hypercube ⋮ The Hitting Time of Multiple Random Walks ⋮ The ANTS problem ⋮ The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks ⋮ Dirichlet Eigenvalues, Local Random Walks, and Analyzing Clusters in Graphs ⋮ On an epidemic model on finite graphs ⋮ Reversible random walks on dynamic graphs ⋮ On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting? ⋮ Multiple random walks on graphs: mixing few to cover many ⋮ Comparison of multiple random walks strategies for searching networks ⋮ A general lower bound for collaborative tree exploration ⋮ The cover time of deterministic random walks for general transition probabilities ⋮ Does adding more agents make a difference? A case study of cover time for the rotor-router

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Covering problems for Brownian motion on spheres
• Comparison theorems for reversible Markov chains
• The electrical resistance of a graph captures its commute and cover times
• Bounds on the cover time
• Asymptotic analysis of a random walk on a hypercube with many dimensions
• The cover time of sparse random graphs
• A stochastic process on the hypercube with applications to peer-to-peer networks
• Tight Bounds for the Cover Time of Multiple Random Walks
• Multiple Random Walks and Interacting Particle Systems
• How Well Do Random Walks Parallelize?
• On the time taken by random walks on finite groups to visit every state
• A Technique for Lower Bounding the Cover Time
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Trading Space for Time in Undirected s-t Connectivity
• A tight upper bound on the cover time for random walks on graphs
• A tight lower bound on the cover time for random walks on graphs
• Many Random Walks Are Faster Than One
• Automata, Languages and Programming
• An Expansion Tester for Bounded Degree Graphs