How Well Do Random Walks Parallelize?

DOI10.1007/978-3-642-03685-9_36zbMath1255.05180OpenAlexW1676511350MaRDI QIDQ3638899

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

zbMATH Keywords

Markov chainsrandom walks

Mathematics Subject Classification ID

Random walks on graphs (05C81) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (11)

Bounds on the cover time of parallel rotor walks ⋮ Broadcasting on paths and cycles ⋮ Coalescing Walks on Rotor-Router Systems ⋮ The Hitting Time of Multiple Random Walks ⋮ The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks ⋮ 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 ⋮ Tight bounds for the cover time of multiple random walks ⋮ Does adding more agents make a difference? A case study of cover time for the rotor-router

This page was built for publication: How Well Do Random Walks Parallelize?