Browsing by Author "Stein, Y."

Filter results by typing the first few letters
Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Minimum Dominating Set Problem for Unit Disks Revisited
    (2015) Carmi, P.; Das, G.K.; Jallu, R.K.; Nandy, S.C.; Prasad, P.R.; Stein, Y.
    In this article, we study approximation algorithms for the problem of computing minimum dominating set for a given set S of n unit disks in R2. We first present a simple O(nlogk) time 5-factor approximation algorithm for this problem, where k is the size of the output. The best known 4-factor and 3-factor approximation algorithms for the same problem run in time O(n8logn) and O(n15logn) 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 O(n6logn). A minor modification of this algorithm produces a 143-factor approximation algorithm in O(n5logn) time. The same techniques can be applied to have a 3-factor and a 4513-factor approximation algorithms in time O(n11logn) and O(n10logn) respectively. Finally, we propose a very important shifting lemma, which is of independent interest, and it helps to present 52-factor approximation algorithm for the same problem. It also helps to improve the time complexity of the proposed PTAS for the problem. 2015 World Scientific Publishing Company.
  • No Thumbnail Available
    Item
    Minimum Dominating Set Problem for Unit Disks Revisited
    (World Scientific, 2015) Carmi, P.; Das, G.K.; Jallu, R.K.; Nandy, S.C.; Prasad, P.R.; Stein, Y.
    In this article, we study approximation algorithms for the problem of computing minimum dominating set for a given set S of n unit disks in R2. We first present a simple O(nlogk) time 5-factor approximation algorithm for this problem, where k is the size of the output. The best known 4-factor and 3-factor approximation algorithms for the same problem run in time O(n8logn) and O(n15logn) 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 O(n6logn). A minor modification of this algorithm produces a 143-factor approximation algorithm in O(n5logn) time. The same techniques can be applied to have a 3-factor and a 4513-factor approximation algorithms in time O(n11logn) and O(n10logn) respectively. Finally, we propose a very important shifting lemma, which is of independent interest, and it helps to present 52-factor approximation algorithm for the same problem. It also helps to improve the time complexity of the proposed PTAS for the problem. © 2015 World Scientific Publishing Company.