Expansion and the cover time of parallel random walks

DOI10.1145/1835698.1835776MaRDI QIDQ5176208zbMATH OpenOpenAlexFDO

Authors Thomas Sauerwald

Publication date 2 March 2015

Published in Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1835698.1835776

zbMATH Keywords

cover timeexpanderexpansionrandom walks

Mathematics Subject Classification ID

Random walks on graphs (05C81) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Recommendations

• How Well Do Random Walks Parallelize?
• Tight bounds for the cover time of multiple random walks
• Many Random Walks Are Faster Than One
• Tight Bounds for the Cover Time of Multiple Random Walks
• Bounds on the cover time

Cites work

• Elastic Transactions
• Software transactional memory
• Toward a theory of transactional contention managers

Cited in

(10)

• Expander properties and the cover time of random intersection graphs
• The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
• Bounds on the cover time of parallel rotor walks
• Random walks which prefer unvisited edges, exploring high girth even degree expanders in linear time
• Expander Properties and the Cover Time of Random Intersection Graphs
• Tight Bounds for the Cover Time of Multiple Random Walks
• Tight bounds for the cover time of multiple random walks
• Multiple random walks on graphs: mixing few to cover many
• Collaboration of random walks on graphs
• Multiple random walks on graphs: mixing few to cover many

Describes a project that uses

Uses Software

• CCSTM

This page was built for publication: Expansion and the cover time of parallel random walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5176208)