Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router.

Adrian Kosowski 1, 2 Dominik Pajak 3, 4
2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
3 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : We consider the problem of graph exploration by a team of $k$ agents, which follow the so-called rotor router mechanism. Agents move in synchronous rounds, and each node successively propagates agents which visit it along its outgoing arcs in round-robin fashion. It has recently been established by Dereniowski et al.\ (STACS 2014) that the rotor-router cover time of a graph $G$, i.e., the number of steps required by the team of agents to visit all of the nodes of $G$, satisfies a lower bound of $\Omega(mD/k)$ and an upper bound of $O(mD/\log k)$ for any graph with $m$ edges and diameter $D$. In this paper, we consider the question of how the cover time of the rotor-router depends on $k$ for many important graph classes. We determine the precise asymptotic value of the rotor-router cover time for all values of $k$ for degree-restricted expanders, random graphs, and constant-dimensional tori. For hypercubes, we also resolve the question precisely, except for values of $k$ much larger than $n$. Our results can be compared to those obtained by Elsässer and Sauerwald (ICALP 2009) in an analogous study of the cover time of $k$ independent parallel random walks in a graph; for the rotor-router, we obtain tight bounds in a slightly broader spectrum of cases. Our proofs take advantage of a relation which we develop, linking the cover time of the rotor-router to the mixing time of the random walk and the local divergence of a discrete diffusion process on the considered graph.
Type de document :
Communication dans un congrès
ICALP 2014 - 41st International Colloquium on Automata, Languages, and Programming, Jul 2014, Copenhagen, Denmark. Springer Verlag, 8573, pp.544-555, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-662-43951-7_46〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00950743
Contributeur : Dominik Pajak <>
Soumis le : mardi 25 mars 2014 - 13:57:00
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : mercredi 25 juin 2014 - 12:05:48

Fichiers

rrcases.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Adrian Kosowski, Dominik Pajak. Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router.. ICALP 2014 - 41st International Colloquium on Automata, Languages, and Programming, Jul 2014, Copenhagen, Denmark. Springer Verlag, 8573, pp.544-555, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-662-43951-7_46〉. 〈hal-00950743v3〉

Partager

Métriques

Consultations de la notice

492

Téléchargements de fichiers

199