Localization game on geometric and planar graphs

Abstract : The main topic of this paper is motivated by a localization problem in cellular networks. Given a graph G we want to localize a walking agent by checking his distance to as few vertices as possible. The model we introduce is based on a pursuit graph game that resembles the famous Cops and Robbers game. It can be considered as a game theoretic variant of the metric dimension of a graph. We provide upper bounds on the related graph invariant ζ(G), defined as the least number of cops needed to localize the robber on a graph G, for several classes of graphs (trees, bipartite graphs, etc). Our main result is that, surprisingly, there exists planar graphs of treewidth 2 and unbounded ζ(G). On a positive side, we prove that ζ(G) is bounded by the pathwidth of G. We then show that the algorithmic problem of determining ζ(G) is NP-hard in graphs with diameter at most 2. Finally, we show that at most one cop can approximate (arbitrary close) the location of the robber in the Euclidean plane.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2018
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01959013
Contributeur : Nicolas Nisse <>
Soumis le : mardi 18 décembre 2018 - 13:46:00
Dernière modification le : dimanche 23 décembre 2018 - 01:11:23

Fichier

Localization Game 171018.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01959013, version 1

Collections

Citation

Bartłomiej Bosek, Przemyslaw Gordinowicz, Jaroslaw Grytczuk, Nicolas Nisse, Joanna Sokol, et al.. Localization game on geometric and planar graphs. Discrete Applied Mathematics, Elsevier, 2018. 〈hal-01959013〉

Partager

Métriques

Consultations de la notice

66

Téléchargements de fichiers

14