Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Liar’s Domination in 2D
verfasst von : Ramesh K. Jallu, Guatam K. Das
Erschienen in: Algorithms and Discrete Applied Mathematics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In this paper we consider Euclidean liar’s domination problem, a variant of dominating set problem. In the Euclidean liar’s domination problem, a set \(\mathcal{P}=\{p_1,p_2,\ldots ,p_n\}\) of n points are given in the Euclidean plane. For \(p \in \mathcal{P}\), N[p] is a subset of \(\mathcal{P}\) such that for any \(q \in N[p]\), the Euclidean distance between p and q is less than or equal to 1. The objective of the Euclidean liar’s domination problem is to find a subset \(D (\subseteq \mathcal{P})\) of minimum size having the following properties: (i) \(|N[p_i] \cap D| \ge 2\) for \(1 \le i \le n\), and (ii) \(|(N[p_i] \cup N[p_j]) \cap D| \ge 3\) for \(i\ne j, 1\le i,j \le n\). We first propose a simple \(O(n\log n)\) time \(\frac{63}{2}\)-factor approximation algorithm for the liar’s domination problem. Next we propose approximation algorithms to improve the approximation factor to \(\frac{732}{k}\) for \(3 \le k \le 183\), and \(\frac{846}{k}\) for \(3 \le k\le 282\). The running time of the algorithms is \(O(n^{k+1}\varDelta )\), where \(\varDelta = \max \{|N[p]| : p\in \mathcal{P}\}\).