[HTML][HTML] Does adding more agents make a difference? A case study of cover time for the rotor-router

A Kosowski, D Pająk - Journal of Computer and System Sciences, 2019 - Elsevier
Journal of Computer and System Sciences, 2019Elsevier
We study the cover time of multiple walks in a graph following the rotor-router mechanism.
This mechanism can be seen as a derandomization of multiple random walks, in which
agents are propagated by nodes to neighbors in round-robin fashion. We provide a
framework for analyzing parallel rotor-router walks, building on the relation of the model to a
continuous diffusion process. We use and extend this approach to the determine the
asymptotic value of the considered cover time for degree-restricted expanders, random …
Abstract
We study the cover time of multiple walks in a graph following the rotor-router mechanism. This mechanism can be seen as a derandomization of multiple random walks, in which agents are propagated by nodes to neighbors in round-robin fashion. We provide a framework for analyzing parallel rotor-router walks, building on the relation of the model to a continuous diffusion process. We use and extend this approach to the determine the asymptotic value of the considered cover time for degree-restricted expanders, random graphs, constant-dimensional tori, and hypercubes.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果