| HAL-Inria | Publications, software ... of Inria's scientists |
Journal articles
The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
Abstract : The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, an agent is initially placed at one of the nodes of the graph. Each node maintains a cyclic ordering of its outgoing arcs, and during successive visits of the agent, propagates it along arcs chosen according to this ordering in round-robin fashion. The behavior of the rotor-router is fully deterministic but its performance characteristics (cover time, return time) closely resemble the expected values of the corresponding parameters of the random walk. In this work Research partially supported by the ANR Project DISPLEXITY (ANR-11-BS02-014). This study has been carried out in the frame of the Investments for the future Programme IdEx Bordeaux-CPU
https://hal.inria.fr/hal-01416011
Contributor : Adrian Kosowski Connect in order to contact the contributor
Submitted on : Tuesday, December 1, 2020 - 5:17:32 PM
Last modification on : Saturday, December 4, 2021 - 3:06:39 AM
Long-term archiving on: : Tuesday, March 2, 2021 - 8:08:04 PM
Contributor : Adrian Kosowski Connect in order to contact the contributor
Submitted on : Tuesday, December 1, 2020 - 5:17:32 PM
Last modification on : Saturday, December 4, 2021 - 3:06:39 AM
Long-term archiving on: : Tuesday, March 2, 2021 - 8:08:04 PM
File
Klasing2017_Article_TheMulti-a...
Explicit agreement for this submission