Many Random Walks Are Faster Than One
From MaRDI portal
Publication:5199503
DOI10.1017/S0963548311000125zbMath1223.05284arXiv0705.0467MaRDI QIDQ5199503
Zvi Lotker, Chen Avin, Michal Koucký, Mark R. Tuttle, Gady Kozma, Noga Alon
Publication date: 16 August 2011
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0705.0467
Related Items
Motifs for Processes on Networks, Analytical results for the distribution of cover times of random walks on random regular graphs, Memory Efficient Anonymous Graph Exploration, Self-Stabilizing and Self-Organizing Virtual Infrastructures for Mobile Networks, Fast distributed algorithms for testing graph properties, A general lower bound for collaborative tree exploration, On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?, Multiple random walks on graphs: mixing few to cover many, Bounds on the cover time of parallel rotor walks, Spanders: distributed spanning expanders, Random walks, bisections and gossiping in circulant graphs, Tight bounds for the cover time of multiple random walks, Active exploration for large graphs, Lower bounds for searching robots, some faulty, Broadcasting on paths and cycles, On an epidemic model on finite graphs, 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, Distributed computation in dynamic networks via random walks, The ANTS problem, Searching without communicating: tradeoffs between performance and selection complexity, The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks, The cover time of a (multiple) Markov chain with rational transition probabilities is rational, Collective search and decision-making for target localization, The Hitting Time of Multiple Random Walks, Coalescing Walks on Rotor-Router Systems
Cites Work
- Covering times of random walks on bounded degree trees and other graphs
- An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM
- Covering problems for Brownian motion on spheres
- Eigenvalues and expanders
- A spectrum of time-space trade-offs for undirected \(s-t\) connectivity
- On the cover time of planar graphs
- Bounds on the cover time
- Lower bounds for covering times for reversible Markov chains and random walks on graphs
- Threshold limits for cover times
- On the time taken by random walks on finite groups to visit every state
- On the Cover Time for Random Walks on Random Graphs
- Fast Connected Components Algorithms for the EREW PRAM
- 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
- An O (log( n ) 4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
