Back to Search
Start Over
Minimum Dominating Set Problem for Unit Disks Revisited.
- Source :
- International Journal of Computational Geometry & Applications; Sep2015, Vol. 25 Issue 3, p227-244, 18p
- Publication Year :
- 2015
-
Abstract
- In this article, we study approximation algorithms for the problem of computing minimum dominating set for a given set of unit disks in . We first present a simple time 5-factor approximation algorithm for this problem, where is the size of the output. The best known 4-factor and 3-factor approximation algorithms for the same problem run in time and respectively [M. De, G. K. Das, P. Carmi and S. C. Nandy, Approximation algorithms for a variant of discrete piercing set problem for unit disks, Int. J. of Computational Geometry and Appl., 22(6):461-477, 2013]. We show that the time complexity of the in-place 4-factor approximation algorithm for this problem can be improved to . A minor modification of this algorithm produces a -factor approximation algorithm in time. The same techniques can be applied to have a 3-factor and a -factor approximation algorithms in time and respectively. Finally, we propose a very important shifting lemma, which is of independent interest, and it helps to present -factor approximation algorithm for the same problem. It also helps to improve the time complexity of the proposed PTAS for the problem. [ABSTRACT FROM AUTHOR]
- Subjects :
- SET theory
PROBLEM solving
COMPUTER algorithms
APPROXIMATION theory
GRAPH theory
Subjects
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 25
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 110339006
- Full Text :
- https://doi.org/10.1142/S0218195915500132