Minimum Set Cover of Sparsely Distributed Sensor Nodes by a Collection of Unit Disks

In this paper, we consider the problem of covering vertices distributed over a two-dimensional plane with as small number of unit disks as possible. This restricted version of the set cover problem is motivated by the problem of reducing the network cost of Wireless Sensor Networks which have been widely used in recent years. The main contribution of the current paper is the proposal of an exact algorithm for solving the minimum set cover by unit disks which outputs an optimum solution in O(n2^{(10/e)√nlog2 n)} time, where ε is the minimum distance between district vertices in the plane. This result indicates that if sensor nodes are "sparsely" distributed over the region so that the distance to the closest sensor is long enough compared with the transmission radius of the base station (i.e., when ε = ω(1√n)), we can significantly reduce the running time of the previous algorithm which solves the ordinary set cover problem in an exact manner.