Sequential Metric Dimension

Julien Bensmail 1 Dorian Mazauric 2 Fionn Mc Inerney 1 Nicolas Nisse 1 Stéphane Pérennes 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
2 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Seager introduced the following game in 2013. An invisible and immobile target is hidden at some vertex of a graph G. Every step, one vertex v of G can be probed which results in the knowledge of the distance between v and the target. The objective of the game is to minimize the number of steps needed to locate the target, wherever it is. We address the generalization of this game where k ≥ 1 vertices can be probed at every step. Our game also generalizes the notion of the metric dimension of a graph. Precisely, given a graph G and two integers k, ≥ 1, the Localization Problem asks whether there exists a strategy to locate a target hidden in G in at most steps by probing at most k vertices per step. We show this problem is NP-complete when k (resp.,) is a fixed parameter. Our main results are for the class of trees where we prove this problem is NP-complete when k and are part of the input but, despite this, we design a polynomial-time (+1)-approximation algorithm in trees which gives a solution using at most one more step than the optimal one. It follows that the Localization Problem is polynomial-time solvable in trees if k is fixed.
Type de document :
Communication dans un congrès
16th Workshop on Approximation and Online Algorithms (WAOA 2018), Aug 2018, Helsinki, Finland
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger
Contributeur : Fionn Mc Inerney <>
Soumis le : vendredi 28 septembre 2018 - 15:20:01
Dernière modification le : lundi 5 novembre 2018 - 15:36:03


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01883712, version 1



Julien Bensmail, Dorian Mazauric, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes. Sequential Metric Dimension. 16th Workshop on Approximation and Online Algorithms (WAOA 2018), Aug 2018, Helsinki, Finland. 〈hal-01883712〉



Consultations de la notice


Téléchargements de fichiers