Minimum Dominating Set for a Point Set in ²

Original · EN

In this article, we consider the problem of computing minimum dominating set for a given set S of n points in ². Here the objective is to find a minimum cardinality subset S' of S such that the union of the unit radius disks centered at the points in S' covers all the points in S. We first propose a simple 4-factor and 3-factor approximation algorithms in O(n⁶ n) and O(n¹¹ n) time respectively improving time complexities by a factor of O(n²) and O(n⁴) respectively over the best known result available in the literature [M. De, G.K. Das, P. Carmi and S.C. Nandy, Approximation algorithms for a variant of discrete piercing set problem for unit disk, Int. J. of Comp. Geom. and Appl., to appear]. Finally, we propose a very important shifting lemma, which is of independent interest and using this lemma we propose a 5/2-factor approximation algorithm and a PTAS for the minimum dominating set problem.