Centroidal localization game

zbMATH Open1406.05068arXiv1711.08836MaRDI QIDQ668034FDOQ668034

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

Publication date: 5 March 2019

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: One important problem in a network is to locate an (invisible) moving entity by using distance-detectors placed at strategical locations. For instance, the metric dimension of a graph $G$ is the minimum number $k$ of detectors placed in some vertices $v_1,cdots,v_k$ such that the vector $(d_1,cdots,d_k)$ of the distances $d(v_i,r)$ between the detectors and the entity's location $r$ allows to uniquely determine $rinV(G)$. In a more realistic setting, instead of getting the exact distance information, given devices placed in $v_1,cdots,v_k$, we get only relative distances between the entity's location $r$ and the devices (for every $1leqi,jleqk$, it is provided whether $d(v_i,r)>$, $<$, or $=$ to $d(v_j,r)$). The centroidal dimension of a graph $G$ is the minimum number of devices required to locate the entity in this setting. We consider the natural generalization of the latter problem, where vertices may be probed sequentially until the moving entity is located. At every turn, a set $v_1,cdots,v_k$ of vertices is probed and then the relative distances between the vertices $v_i$ and the current location $r$ of the entity are given. If not located, the moving entity may move along one edge. Let $zet{a}^{*}(G)$ be the minimum $k$ such that the entity is eventually located, whatever it does, in the graph $G$. We prove that $zet{a}^{\ast }(T)leq2$ for every tree $T$ and give an upper bound on $zet{a}^{\ast }(GsquareH)$ in cartesian product of graphs $G$ and $H$. Our main result is that $zet{a}^{\ast }(G)leq3$ for any outerplanar graph $G$. We then prove that $zet{a}^{*}(G)$ is bounded by the pathwidth of $G$ plus 1 and that the optimization problem of determining $zet{a}^{*}(G)$ is NP-hard in general graphs. Finally, we show that approximating (up to any constant distance) the entity's location in the Euclidean plane requires at most two vertices per turn.

Full work available at URL: https://arxiv.org/abs/1711.08836

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Sequential metric dimension
• Localization game on geometric and planar graphs
• Sequential metric dimension
• Centroidal bases in graphs
• Locating a robber on a graph

zbMATH Keywords

graph searchingouterplanar graphscops and robber

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cites Work

• The game of cops and robbers on graphs
• On a new class of codes for identifying vertices in graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Locating a robber on a graph via distance queries
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Domination and location in acyclic graphs
• Locating a robber on a graph
• Title not available (Why is that?)
• Locating a robber with multiple probes
• Locating a backtracking robber on a tree
• Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
• Localization game on geometric and planar graphs
• A robber locating strategy for trees
• Centroidal bases in graphs

Cited In (13)

• The localization game on oriented graphs
• The localization capture time of a graph
• Approximately locating an invisible agent in a graph with relative distance queries
• Localization game for random graphs
• Some Stackelberg type location game
• The localization game on Cartesian products
• A sequential locating game on graphs
• Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
• The localization number of designs
• The one-visibility localization game
• Edge and pair queries-random graphs and complexity
• Centroidal bases in graphs
• Sequential metric dimension

This page was built for publication: Centroidal localization game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q668034)