In this article, we consider the problem of computing minimum dominating set for a given set @math of @math points in @math . Here the objective is to find a minimum cardinality subset @math of @math such that the union of the unit radius disks centered at the points in @math covers all the points in @math . We first propose a simple 4-factor and 3-factor approximation algorithms in @math and @math time respectively improving time complexities by a factor of @math and @math 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 @math -factor approximation algorithm and a PTAS for the minimum dominating set problem.
108-approximation algorithm [C a , 2004 @cite_4 ] 72-approximation algorithm [Narayanappa and Voytechovsky, 2006 @cite_20 ] 38-approximation algorithm in O( @math ) time [, 2007 @cite_18 ] 22-approximation algorithm in O( @math ) time [, 2010 @cite_1 ] 18-approximation algorithm in O( @math ) time [, 2012 @cite_5 ] 15-approximation algorithm in O( @math ) time [Fraser and L ' o pez-Ortiz, 2012 @cite_8 ] @math -approximation algorithm in @math time [, 2013 @cite_26 ]
@cite_18 @cite_26 @cite_4 @cite_8 @cite_1 @cite_5 @cite_20
2175864873 2021544892 2592261725 2106734202 1998920351 2138222927
In this paper we consider the discrete unit disk cover problem and the rectangular region cover problem as follows. Broadcasting is a fundamental operation which is frequent in wireless ad hoc networks. A simple broadcasting mechanism, known as flooding, is to let every node retransmit the message to all its 1-hop neighbors when receiving the first copy of the message. Despite its simplicity, flooding is very inefficient and can result in high redundancy, contention, and collision. One approach to reducing the redundancy is to let each node forward the message only to a small subset of 1-hop neighbors that cover all of the node's 2-hop neighbors. In this paper we propose two practical heuristics for selecting the minimum number of forwarding neighbors: an O(n log n)time algorithm that selects at most 6 times more forwarding neighbors than the optimum, and an O(n log2 n) time algorithm with an improved approximation ratio of 3, where n is the number of 1- and 2-hop neighbors. The best previously known algorithm, due to Bronnimann and Goodrich [2], guarantees O(1) approximation in O(n3 log n)time. We present a study of the Within-Strip Discrete Unit Disk Cover (WSDUDC) problem, which is a restricted version of the Discrete Unit Disk Cover (DUDC) problem. For the WSDUDC problem, there exists a set of points and a set of unit disks in the plane, and the points and disk centres are conned to a strip of xed height. An optimal solution to the WSDUDC problem is a set of disks of minimum cardinality that covers all points in the input set. We describe a range of approximation algorithms for the problem, including 4- and 3-approximate algorithms which apply for strips of height 2 p 2=3 0:94 and 0:8 units respectively, as well as a general scheme for any strip with less than unit height. We prove that the WSDUDC problem is NP-complete on strips of any xed height, which is our most interesting result from a theoretical standpoint. The result is also quite surprising, since a number of similar problems are tractable on strips of xed height. Finally, we discuss how these results may be applied to known DUDC approximation algorithms. Given a set @math of m unit disks and a set @math of n points in the plane, the discrete unit disk cover problem is to select a minimum cardinality subset @math to cover @math . This problem is NP-hard [14] and the best previous practical solution is a 38-approximation algorithm by [5]. We first consider the line-separable discrete unit disk cover problem (the set of disk centers can be separated from the set of points by a line) for which we present an O(n(log n + m))-time algorithm that finds an exact solution. Combining our line-separable algorithm with techniques from the algorithm of [5] results in an O(m2n4) time 22-approximate solution to the discrete unit disk cover problem. Given a set of n points and a set of m unit disks on a 2-dimensional plane, the discrete unit disk cover (DUDC) problem is (i) to check whether each point in is covered by at least one disk in or not and (ii) if so, then find a minimum cardinality subset such that the unit disks in cover all the points in . The discrete unit disk cover problem is a geometric version of the general set cover problem which is NP-hard. The general set cover problem is not approximable within , for some constant c, but the DUDC problem was shown to admit a constant factor approximation. In this paper, we provide an algorithm with constant approximation factor 18. The running time of the proposed algorithm is . The previous best known tractable solution for the same problem was a 22-factor approximation algorithm with running time . We present a polynomial time algorithm for the unit disk covering problem with an approximation factor 72, and show that this is the best possible approximation factor based on the method used. This is an improvement on the best known approximation factor of 108.