How Well Do Random Walks Parallelize?

DOI10.1007/978-3-642-03685-9_36MaRDI QIDQ3638899zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Markov chainsrandom walks

Mathematics Subject Classification ID

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

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

Cited in

(22)

• On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
• The power of two choices for random walks
• Cover time and mixing time of random walks on dynamic graphs
• Bounds on the cover time of parallel rotor walks
• Broadcasting on paths and cycles
• The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
• 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
• Multiple Random Walks and Interacting Particle Systems
• On an epidemic model on finite graphs
• Random walks on colored graphs
• Spread of information and diseases via random walks in sparse graphs
• Multiple random walks on paths and grids
• Multiple random walks on graphs: mixing few to cover many
• Reversible random walks on dynamic graphs
• Coalescing walks on rotor-router systems
• The hitting time of multiple random walks
• Tight Bounds for the Cover Time of Multiple Random Walks
• Multiple lazy random walks on cycles
• Multiple random walks in random regular graphs
• Expansion and the cover time of parallel random walks
• Speeding up random walks with neighborhood exploration

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)