{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T11:12:53Z","timestamp":1649157173676},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2016,11]]},"abstract":"<jats:p> A connected dominating set (CDS, for short) for graph G is a dominating set which induces a connected subgraph of G. In this paper, we consider the problem of finding a minimum CDS for unit disk graphs, which have recently attracted considerable attention as a model of virtual backbone in multi-hop wireless networks. This optimization problem is known to be NP-hard and many approximation algorithms have been proposed in the literature. This paper proves a lower bound on the performance ratio of a greedy algorithm of Guha and Khuller which was originally proposed for general graphs and is known to be a representative in which the lookahead plays a crucial role in selecting a vertex to be contained in the CDS. More specifically, we show that for any fixed <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\" altimg=\"eq-00001.gif\"><mml:mrow><mml:mi>\u03b5<\/mml:mi><mml:mo>&gt;<\/mml:mo><mml:mn>0<\/mml:mn><\/mml:mrow><\/mml:math> and integer <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\" altimg=\"eq-00002.gif\"><mml:mrow><mml:msub><mml:mi>n<\/mml:mi><mml:mn>0<\/mml:mn><\/mml:msub><mml:mo>\u2265<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:math>, there is a unit disk graph with bounded degree consisting of at least <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\" altimg=\"eq-00003.gif\"><mml:mrow><mml:msub><mml:mi>n<\/mml:mi><mml:mn>0<\/mml:mn><\/mml:msub><\/mml:mrow><\/mml:math> vertices for which the output of the greedy algorithm is no better than <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\" altimg=\"eq-00004.gif\"><mml:mrow><mml:mn>3<\/mml:mn><mml:mo>\u2212<\/mml:mo><mml:mi>\u03b5<\/mml:mi><\/mml:mrow><\/mml:math> times of an optimum solution to the same graph. <\/jats:p>","DOI":"10.1142\/s0129054116500325","type":"journal-article","created":{"date-parts":[[2017,1,24]],"date-time":"2017-01-24T05:57:32Z","timestamp":1485237452000},"page":"829-843","source":"Crossref","is-referenced-by-count":0,"title":["On the Power of Lookahead in Greedy Scheme for Finding a Minimum CDS for Unit Disk Graphs"],"prefix":"10.1142","volume":"27","author":[{"given":"Satoshi","family":"Fujita","sequence":"first","affiliation":[{"name":"Institute of Engineering, Hiroshima University, Kagamiyama 1-4-1, Higashi-Hiroshima, 739-8527, Japan"}]}],"member":"219","published-online":{"date-parts":[[2017,1,23]]},"reference":[{"key":"p_1","first-page":"3849","volume":"2002","author":"Alzoubi K. M.","journal-title":"Proc. of the 35th Hawaii International Conference on System Sciences (HICSS )"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.10097"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"p_5","first-page":"34","volume":"1997","author":"Das B.","journal-title":"Proc. of the 6th International Conference on Computers and Communications Networks (ICCCN )"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.177"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13705"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009201"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0903"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1002\/wcm.356"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88582-5_18"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-005-8466-1"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2009.78"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1109\/71.980024"},{"key":"p_16","first-page":"1597","volume":"02","author":"Wan P.-J.","year":"2002","journal-title":"Proc. of INFOCOM '"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2227791"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.08.037"},{"key":"p_20","first-page":"154","volume":"5258","author":"Zhang Z.","year":"2008","journal-title":"LNCS"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054116500325","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T02:52:04Z","timestamp":1565146324000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054116500325"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11]]},"references-count":18,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2017,1,23]]},"published-print":{"date-parts":[[2016,11]]}},"alternative-id":["10.1142\/S0129054116500325"],"URL":"https:\/\/doi.org\/10.1142\/s0129054116500325","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11]]}}}