Bounds on the cover time of parallel rotor walks

作者：

Highlights：

• We consider the cover time of multi-agent rotor-router.

• Rotor-router is a deterministic process in which the environment determines moves of the agents.

• Rotor-router is a form of derandomization of the random walk.

• We show that k agents explore any graph between Θ(log⁡k) and Θ(k) faster than single agent.

• It is conjectured that the speedup for multiple random walks is also between Θ(log⁡k) and Θ(k).

摘要

•We consider the cover time of multi-agent rotor-router.•Rotor-router is a deterministic process in which the environment determines moves of the agents.•Rotor-router is a form of derandomization of the random walk.•We show that k agents explore any graph between Θ(log⁡k) and Θ(k) faster than single agent.•It is conjectured that the speedup for multiple random walks is also between Θ(log⁡k) and Θ(k).

论文关键词：Distributed graph exploration,Rotor-router,Cover time,Collaborative robots,Parallel random walks,Derandomization

论文评审过程：Received 18 December 2014, Revised 11 January 2016, Accepted 29 January 2016, Available online 9 March 2016, Version of Record 1 April 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.01.004