Liar's Domination in 2D

0534918 - ÚI 2021 CH eng C - Conference Paper (international conference)
Jallu, Ramesh Kumar - Das, G. K.
Liar's Domination in 2D.
Algorithms and Discrete Applied Mathematics. Cham: Springer, 2017 - (Narayanaswamy, N.; Gaur, D.), s. 219-229. Lecture Notes in Computer Science, 10156. ISBN 978-3-319-53006-2. ISSN 0302-9743.
[CALDAM 2017. International Conference /3./. Sancoale, Goa (IN), 16.02.2017-18.02.2017]
Keywords : graphs * approximation * algorithms * Unit disk graph * Approximation algorithm * Dominating set * Liar's dominating set

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 P = {p(1), p(2),..., p(n)} of n points are given in the Euclidean plane. For p is an element of P, N[p] is a subset of P such that for any q is an element of 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(. P) of minimum size having the following properties: (i) |N[p(i)] boolean AND D| >= 2 for 1 <= i <= n, and (ii) |(N[p(i)]boolean OR N[p(j)]) n D| = 3 for i not equal j, 1 <= i, j <= n. We first propose a simple O(n log n) time 63/2-factor approximation algorithm for the liar's domination problem. Next we propose approximation algorithms to improve the approximation factor to 732 k for 3 <= k <= 183, and 846/k for 3 <= k <= 282. The running time of the algorithms is O(n(k+1) Delta), where Delta = max{|N[p]| : p is an element of P}.
Permanent Link: http://hdl.handle.net/11104/0313055