Expansion and the cover time of parallel random walks

DOI10.1145/1835698.1835776zbMATH Open1315.05128OpenAlexW2007075970MaRDI QIDQ5176208FDOQ5176208

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

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

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)

Cites Work

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

Cited In (8)

• 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
• Bounds on the cover time of parallel rotor walks
• Tight bounds for the cover time of multiple random walks
• Expander Properties and the Cover Time of Random Intersection Graphs
• Multiple random walks on graphs: mixing few to cover many
• Random walks which prefer unvisited edges, exploring high girth even degree expanders in linear time
• Tight Bounds for the Cover Time of Multiple Random Walks

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)