Localization game on geometric and planar graphs

Bartłomiej Bosek , Przemysław Gordinowicz , Jarosław Grytczuk , Nicolas Nisse , Joanna Chybowska-Sokół , Małgorzata Śleszyńska-Nowak

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.
Author Bartłomiej Bosek
Bartłomiej Bosek,,
-
, Przemysław Gordinowicz
Przemysław Gordinowicz,,
-
, Jarosław Grytczuk (FMIS / DAC)
Jarosław Grytczuk,,
- Department of Algebra and Combinatorics
, Nicolas Nisse
Nicolas Nisse,,
-
, Joanna Chybowska-Sokół
Joanna Chybowska-Sokół,,
-
, Małgorzata Śleszyńska-Nowak (FMIS / DIPS)
Małgorzata Śleszyńska-Nowak,,
- Department of Information Processing Systems
Journal seriesDiscrete Applied Mathematics, ISSN 0166-218X, (A 25 pkt)
Issue year2018
Vol251
Pages30-39
Publication size in sheets0.5
Keywords in Polishgra lokalizacyjna, lokalizacja w sieciach komórkowych, gra w policjantów i złodziei
Keywords in Englishlocalization game, localization in cellular networks, Cops and Robbers game
ASJC Classification2604 Applied Mathematics; 2607 Discrete Mathematics and Combinatorics
Abstract in PolishGłównym tematem artykułu jest problem lokalizacji w sieciach komórkowych. Dla danego grafu G chcemy zlokalizować poruszający się obiekt przez sprawdzanie jego odległości od możliwie najmniejszej liczby wierzchołków. Wprowadzony przez nas model opiera się na grafowej grze, która przypomina słynną grę w policjantów i złodziei. W pracy pokazujemy górne ograniczenie na ζ (G) - zdefiniowane jako najmniejsza liczba policjantów potrzebna do zlokalizowania złodzieja w grafie G. Nasze twierdzenia obejmują różne klasy grafów, jak np. drzewa i grafy dwudzielne. Głównym wynikiem w pracy jest pokazanie, że istnieje planarny graf o szerokości drzewowej 2 i nieoograniczonym ζ (G). Udowodniliśmy także, że ζ (G) jest ograniczone przez szerokość ścieżkową grafu. Pokazaliśmy również, że algorytmiczny problem znalezienia ζ (G) jest NP-trudny dla grafów o średnicy co najwyżej 2. Ostatni wynik mówi o tym, że 1 policjant może dowolnie dokładnie przybliżyć pozycję złodzieja na płaszczyźnie Euklidesowej.
DOIDOI:10.1016/j.dam.2018.04.017
URL https://www.sciencedirect.com/science/article/pii/S0166218X18302373
Languageen angielski
Score (nominal)25
ScoreMinisterial score = 25.0, 12-03-2019, ArticleFromJournal
Ministerial score (2013-2016) = 25.0, 12-03-2019, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.17; WoS Impact Factor: 2017 = 0.932 (2) - 2017=1.008 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back