Localiser une cible dans un graphe

Julien Bensmail 1, 2 Dorian Mazauric 3, 2 Fionn Mc Inerney 1, 2 Nicolas Nisse 1, 2 Stéphane Pérennes 1, 2
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
3 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : Le jeu de la localisation d'une cible (invisible et immobile) dans un graphe a été introduit par Seager en 2013. Dans ce jeu, une cible est placée secrètement sur un sommet et, à chaque tour, il est possible d'interroger un sommet et recevoir, comme réponse, la distance exacte entre ce sommet et la cible. L'objectif est de localiser la cible en minimisant le nombre de tours, et ce, quelle que soit sa position. Nous considérons une généralisation de ce jeu où k sommets peuvent être interrogés à chaque tour. Celle-ci est notamment liée à la notion de dimension métrique d'un graphe. Nous étudions aussi la variante où les distances relatives sont données comme réponses, qui généralise la dimension centroïdale des graphes. Pour les deux variantes, nous montrons que localiser la cible en un nombre minimum de tours est NP-complet en général, lorsque k est fixé. Dans le cas des arbres (à n noeuds) et des distances exactes, nous montrons que le problème est NP-complet lorsque k fait partie de l'entrée. Nous donnons cependant une (+1)-approximation de ce problème : nous présentons un algorithme qui, en temps O(n log n) (indépendant de k), calcule une stratégie pour localiser la cible en au plus un tour de plus que l'optimal. Cet algorithme peut aussi être utilisé pour résoudre exactement le problème en temps $n^{O(k)}$.
Type de document :
Communication dans un congrès
ALGOTEL 2018 - 20èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2018, Roscoff, France
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01774827
Contributeur : Dorian Mazauric <>
Soumis le : mardi 24 avril 2018 - 08:48:23
Dernière modification le : mercredi 25 avril 2018 - 01:32:59

Fichier

algotel_localizationRevised.pd...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01774827, version 1

Collections

Citation

Julien Bensmail, Dorian Mazauric, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes. Localiser une cible dans un graphe. ALGOTEL 2018 - 20èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2018, Roscoff, France. 〈hal-01774827〉

Partager

Métriques

Consultations de la notice

128

Téléchargements de fichiers

33