The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks

DOI10.1145/2484239.2484260MaRDI QIDQ5176115zbMATH OpenOpenAlexFDO

Authors Ralf Klasing, Adrian Kosowski, Dominik Pajak, Thomas Sauerwald

Publication date 2 March 2015

Published in Proceedings of the 2013 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

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

zbMATH Keywords

graph explorationparallel explorationpropp machinerandom walkringrotor walk

Mathematics Subject Classification ID

Random walks on graphs (05C81) Network design and communication in computer systems (68M10) Distributed systems (68M14) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• 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
• Bounds on the cover time of parallel rotor walks
• Limit behavior of the multi-agent rotor-router system
• Bounds on the cover time of parallel rotor walks

Cited in

(11)

• Limit behavior of the multi-agent rotor-router system
• Does adding more agents make a difference? A case study of cover time for the rotor-router
• The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
• Robustness of the rotor-router mechanism
• Bounds on the cover time of parallel rotor walks
• Bounds on the cover time of parallel rotor walks
• Coalescing walks on rotor-router systems
• Unbounded discrepancy of deterministic random walks on grids
• Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router
• Multiple random walks on graphs: mixing few to cover many
• Multiple random walks on graphs: mixing few to cover many

This page was built for publication: The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks

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