How Well Do Random Walks Parallelize?
From MaRDI portal
Publication:3638899
DOI10.1007/978-3-642-03685-9_36zbMATH Open1255.05180OpenAlexW1676511350MaRDI QIDQ3638899FDOQ3638899
Authors: Klim Efremenko, Omer Reingold 
Publication date: 28 October 2009
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03685-9_36
Recommendations
- scientific article; zbMATH DE number 1971718
- Fast distributed random walks
- How to compute times of random walks based distributed algorithms
- Does a random walker meet universality?
- Efficient distributed random walks with applications
- Distributed random walks
- scientific article; zbMATH DE number 975592
- How many probes are needed to compute the maximum of a random walk?
- scientific article; zbMATH DE number 850235
Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Random walks on graphs (05C81)
Cited In (18)
- Speeding up random walks with neighborhood exploration
- The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
- Coalescing Walks on Rotor-Router Systems
- Bounds on the cover time of parallel rotor walks
- Spread of information and diseases via random walks in sparse graphs
- On an epidemic model on finite graphs
- Does adding more agents make a difference? A case study of cover time for the rotor-router
- Tight bounds for the cover time of multiple random walks
- Broadcasting on paths and cycles
- Multiple Random Walks and Interacting Particle Systems
- On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
- The Hitting Time of Multiple Random Walks
- Reversible random walks on dynamic graphs
- Multiple random walks on graphs: mixing few to cover many
- Multiple random walks in random regular graphs
- Tight Bounds for the Cover Time of Multiple Random Walks
- Random walks on colored graphs
- The power of two choices for random walks
This page was built for publication: How Well Do Random Walks Parallelize?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638899)
