Tight bounds for the cover time of multiple random walks

DOI10.1016/j.tcs.2010.08.010zbMath1227.68030MaRDI 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

graph; random walk; parallel; cover time; speed-up

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C81: Random walks on graphs

Related Items

A general lower bound for collaborative tree exploration, Bounds on the cover time of parallel rotor walks, Comparison of multiple random walks strategies for searching networks, 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, 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, The Hitting Time of Multiple Random Walks, Coalescing Walks on Rotor-Router Systems

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