Expansion and the cover time of parallel random walks

DOI10.1145/1835698.1835776zbMath1315.05128OpenAlexW2007075970MaRDI QIDQ5176208

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 walksexpandercover time

Mathematics Subject Classification ID

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

Related Items (3)

Bounds on the cover time of parallel rotor walks ⋮ The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks ⋮ Multiple random walks on graphs: mixing few to cover many

Uses Software

• CCSTM

Cites Work

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

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