Graph Searching with advice

Nicolas Nisse 1 David Soguet 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Fraigniaud {\it et al.} (2006) introduced a new measure of difficulty for a distributed task in a network. The smallest {\it number of bits of advice} of a distributed problem is the smallest number of bits of information that has to be available to nodes in order to accomplish the task efficiently. Our paper deals with the number of bits of advice required to perform efficiently the graph searching problem in a distributed setting. In this variant of the problem, all searchers are initially placed at a particular node of the network. The aim of the team of searchers is to capture an invisible and arbitrarily fast fugitive in a monotone connected way, i.e., the cleared part of the graph is permanently connected, and never decreases while the search strategy is executed. We show that the minimum number of bits of advice permitting the monotone connected clearing of a network in a distributed setting is $O (n \log n)$, where $n$ is the number of nodes of the network, and this bound is tight. More precisely, we first provide a labelling of the vertices of any graph $G$, using a total of $O(n \log n)$ bits, and a protocol using this labelling that enables clearing $G$ in a monotone connected distributed way. Then, we show that this number of bits of advice is almost optimal: no protocol using an oracle providing $o(n \log n)$ bits of advice permits the monotone connected clearing of a network using the smallest number of searchers.
Type de document :
Communication dans un congrès
International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2007, Castiglioncello, Italy. 2007
Liste complète des métadonnées

https://hal.inria.fr/inria-00423450
Contributeur : Nicolas Nisse <>
Soumis le : samedi 10 octobre 2009 - 13:40:42
Dernière modification le : vendredi 12 janvier 2018 - 01:49:34

Identifiants

  • HAL Id : inria-00423450, version 1

Citation

Nicolas Nisse, David Soguet. Graph Searching with advice. International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2007, Castiglioncello, Italy. 2007. 〈inria-00423450〉

Partager

Métriques

Consultations de la notice

153