Collision-Free Network Exploration

Jurek Czyzowicz 1 Dariusz Dereniowski 2 Leszek Gasieniec 3 Ralf Klasing 4, 5 Adrian Kosowski 6, 7, 4, 5 Dominik Pajak 4, 5
4 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
6 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : A set of mobile agents is placed at different nodes of a $n$-node network. The agents synchronously move along the network edges in a {\em collision-free} way, i.e., in no round may two agents occupy the same node. In each round, an agent may choose to stay at its currently occupied node or to move to one of its neighbors. An agent has no knowledge of the number and initial positions of other agents. We are looking for the shortest possible time required to complete the collision-free {\em network exploration}, i.e., to reach a configuration in which each agent is guaranteed to have visited all network nodes and has returned to its starting location. We first consider the scenario when each mobile agent knows the map of the network, as well as its own initial position. We establish a connection between the number of rounds required for collision-free exploration and the degree of the minimum-degree spanning tree of the graph. We provide tight (up to a constant factor) lower and upper bounds on the collision-free exploration time in general graphs, and the exact value of this parameter for trees. For our second scenario, in which the network is unknown to the agents, we propose collision-free exploration strategies running in $O(n^2)$ rounds for tree networks and in $O(n^5\log n)$ rounds for general networks.
Type de document :
Communication dans un congrès
LATIN - 11th Latin American Theoretical INformatics Symposium, Mar 2014, Montevideo, Uruguay. Springer, 8392, pp.342-354, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-642-54423-1_30〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00736276
Contributeur : Dominik Pajak <>
Soumis le : jeudi 27 septembre 2012 - 23:53:38
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 18:08:25

Fichiers

collision-free-exploration.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Relations

Citation

Jurek Czyzowicz, Dariusz Dereniowski, Leszek Gasieniec, Ralf Klasing, Adrian Kosowski, et al.. Collision-Free Network Exploration. LATIN - 11th Latin American Theoretical INformatics Symposium, Mar 2014, Montevideo, Uruguay. Springer, 8392, pp.342-354, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-642-54423-1_30〉. 〈hal-00736276〉

Partager

Métriques

Consultations de la notice

666

Téléchargements de fichiers

237