{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,15]],"date-time":"2024-06-15T11:54:40Z","timestamp":1718452480793},"reference-count":26,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2015,9]]},"abstract":" In this article, we study approximation algorithms for the problem of computing minimum dominating set for a given set [Formula: see text] of [Formula: see text] unit disks in [Formula: see text]. We first present a simple [Formula: see text] time 5-factor approximation algorithm for this problem, where [Formula: see text] is the size of the output. The best known 4-factor and 3-factor approximation algorithms for the same problem run in time [Formula: see text] and [Formula: see text] 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\u2013477, 2013]. We show that the time complexity of the in-place 4-factor approximation algorithm for this problem can be improved to [Formula: see text]. A minor modification of this algorithm produces a [Formula: see text]-factor approximation algorithm in [Formula: see text] time. The same techniques can be applied to have a 3-factor and a [Formula: see text]-factor approximation algorithms in time [Formula: see text] and [Formula: see text] respectively. Finally, we propose a very important shifting lemma, which is of independent interest, and it helps to present [Formula: see text]-factor approximation algorithm for the same problem. It also helps to improve the time complexity of the proposed PTAS for the problem. <\/jats:p>","DOI":"10.1142\/s0218195915500132","type":"journal-article","created":{"date-parts":[[2015,10,15]],"date-time":"2015-10-15T03:17:40Z","timestamp":1444879060000},"page":"227-244","source":"Crossref","is-referenced-by-count":5,"title":["Minimum Dominating Set Problem for Unit Disks Revisited"],"prefix":"10.1142","volume":"25","author":[{"given":"Paz","family":"Carmi","sequence":"first","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva - 84105, Israel"}]},{"given":"Gautam K.","family":"Das","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Indian Institute of Technology Guwahati, Guwahati - 781039, India"}]},{"given":"Ramesh K.","family":"Jallu","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Indian Institute of Technology Guwahati, Guwahati - 781039, India"}]},{"given":"Subhas C.","family":"Nandy","sequence":"additional","affiliation":[{"name":"Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata - 700108, India"}]},{"given":"Prajwal R.","family":"Prasad","sequence":"additional","affiliation":[{"name":"National Institute of Technology Karnataka, Mangalore - 575025, India"}]},{"given":"Yael","family":"Stein","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva - 84105, Israel"}]}],"member":"219","published-online":{"date-parts":[[2015,10,15]]},"reference":[{"key":"p_1","first-page":"193","volume":"33","author":"Acharyya R.","year":"2015","journal-title":"J. Dis. Alg."},{"key":"p_2","first-page":"4110","author":"Amb\u00fchl C.","year":"2006","journal-title":"Spain"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.05.004"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1023\/B:MONE.0000013622.63511.57"},{"key":"p_7","first-page":"4835","author":"Carmi P.","year":"2007","journal-title":"Japan"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.01.001"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"p_10","first-page":"77","volume":"2","author":"Claude F.","year":"2010","journal-title":"Discr. Math. Alg. Appl."},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1142\/S021819591350009X"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195912500094"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.11.015"},{"key":"p_15","first-page":"53","author":"Fraser R.","year":"2012","journal-title":"Canada"},{"key":"p_16","first-page":"7846","author":"da Fonseca G. D.","year":"2012","journal-title":"Slovenia"},{"key":"p_18","first-page":"6347","author":"Gibson M.","year":"2010","journal-title":"United Kingdom"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-008-9146-0"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90018-9"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230250205"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9285-9"},{"key":"p_24","first-page":"3879","author":"Nieberg T.","year":"2005","journal-title":"Spain"},{"key":"p_25","first-page":"15","author":"Narayanappa S.","year":"2006","journal-title":"Canada"},{"key":"p_27","first-page":"475","author":"Raz R.","year":"1997","journal-title":"Texas, USA"},{"key":"p_28","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1965-018-9"},{"key":"p_29","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.06.022"}],"container-title":["International Journal of Computational Geometry & Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195915500132","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:39:11Z","timestamp":1565131151000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195915500132"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9]]},"references-count":26,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2015,10,15]]},"published-print":{"date-parts":[[2015,9]]}},"alternative-id":["10.1142\/S0218195915500132"],"URL":"https:\/\/doi.org\/10.1142\/s0218195915500132","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9]]}}}