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

expansionrandom walkscover timeexpander

Mathematics Subject Classification ID

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

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

(8)

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

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)