Many Random Walks Are Faster Than One

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

zbMATH Keywords

distributed computing

Mathematics Subject Classification ID

Distributed systems (68M14) Random walks on graphs (05C81)

Related Items (26)

Bounds on the cover time of parallel rotor walks ⋮ Collective search and decision-making for target localization ⋮ Analytical results for the distribution of cover times of random walks on random regular graphs ⋮ Broadcasting on paths and cycles ⋮ Memory Efficient Anonymous Graph Exploration ⋮ Coalescing Walks on Rotor-Router Systems ⋮ The Hitting Time of Multiple 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 ⋮ On an epidemic model on finite graphs ⋮ The cover time of a (multiple) Markov chain with rational transition probabilities is rational ⋮ Spanders: distributed spanning expanders ⋮ On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting? ⋮ Multiple random walks on graphs: mixing few to cover many ⋮ Self-Stabilizing and Self-Organizing Virtual Infrastructures for Mobile Networks ⋮ Random walks, bisections and gossiping in circulant graphs ⋮ Lower bounds for searching robots, some faulty ⋮ Active exploration for large graphs ⋮ Tight bounds for the cover time of multiple random walks ⋮ Fast distributed algorithms for testing graph properties ⋮ 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 ⋮ Distributed computation in dynamic networks via random walks ⋮ Motifs for Processes on Networks

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

This page was built for publication: Many Random Walks Are Faster Than One