{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T20:39:39Z","timestamp":1769978379757,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642157745","type":"print"},{"value":"9783642157752","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15775-2_21","type":"book-chapter","created":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T14:47:32Z","timestamp":1283352452000},"page":"243-254","source":"Crossref","is-referenced-by-count":33,"title":["Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier"],"prefix":"10.1007","author":[{"given":"Matt","family":"Gibson","sequence":"first","affiliation":[]},{"given":"Imran A.","family":"Pirwani","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/11830924_3","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"C. Amb\u00fchl","year":"2006","unstructured":"Amb\u00fchl, C., Erlebach, T., Mihal\u00e1k, M., Nunkesser, M.: Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol.\u00a04110, pp. 3\u201314. Springer, Heidelberg (2006)"},{"issue":"3","key":"21_CR2","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F. Aurenhammer","year":"1991","unstructured":"Aurenhammer, F.: Voronoi diagrams\u2014a survey of a fundamental geometric data structure. ACM Comput. Surv.\u00a023(3), 345\u2013405 (1991)","journal-title":"ACM Comput. Surv."},{"issue":"2","key":"21_CR3","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"T.M. Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms\u00a046(2), 178\u2013189 (2003)","journal-title":"J. Algorithms"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. In: SoCG 2009, pp. 333\u2013340 (2009)","DOI":"10.1145\/1542362.1542420"},{"key":"21_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1007\/978-3-540-30140-0_19","volume-title":"Algorithms \u2013 ESA 2004","author":"M. Chleb\u00edk","year":"2004","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of dominating set problems. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 192\u2013203. Springer, Heidelberg (2004)"},{"issue":"1-3","key":"21_CR6","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B.N. Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Mathematics\u00a086(1-3), 165\u2013177 (1990)","journal-title":"Discrete Mathematics"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: Applications of random sampling in computational geometry, II. In: Symposium on Computational Geometry, pp. 1\u201311 (1988)","DOI":"10.1145\/73393.73394"},{"issue":"6","key":"21_CR8","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1137\/S0097539702402676","volume":"34","author":"T. Erlebach","year":"2005","unstructured":"Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput.\u00a034(6), 1302\u20131323 (2005)","journal-title":"SIAM J. Comput."},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/978-3-540-78773-0_64","volume-title":"LATIN 2008: Theoretical Informatics","author":"T. Erlebach","year":"2008","unstructured":"Erlebach, T., van Leeuwen, E.J.: Domination in geometric intersection graphs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol.\u00a04957, pp. 747\u2013758. Springer, Heidelberg (2008)"},{"issue":"4","key":"21_CR10","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"21_CR11","unstructured":"Gibson, M., Pirwani, I.A.: Approximation algorithms for dominating set in disk graphs. CoRR\u00a0abs\/1004.3320 (2010)"},{"issue":"2","key":"21_CR12","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"H.B. Hunt III","year":"1998","unstructured":"Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: Nc-approximation schemes for np- and pspace-hard problems for geometric graphs. J. Algorithms\u00a026(2), 238\u2013274 (1998)","journal-title":"J. Algorithms"},{"issue":"2","key":"21_CR13","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-sat. J. Comput. Syst. Sci.\u00a062(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"Kammer, F., Tholey, T.: Approximation algorithms for intersection graphs. To appear in APPROX-RANDOM (2010)","DOI":"10.1007\/978-3-642-15369-3_20"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Marx, D.: On the optimality of planar and geometric approximation schemes. In: FOCS, pp. 338\u2013348 (2007)","DOI":"10.1109\/FOCS.2007.26"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Mustafa, N.H., Ray, S.: PTAS for geometric hitting set problems via local search. In: SoCG, pp. 17\u201322 (2009)","DOI":"10.1145\/1542362.1542367"},{"issue":"4","key":"21_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1383369.1383380","volume":"4","author":"T. Nieberg","year":"2008","unstructured":"Nieberg, T., Hurink, J., Kern, W.: Approximation schemes for wireless networks. ACM Transactions on Algorithms\u00a04(4), 1\u201317 (2008)","journal-title":"ACM Transactions on Algorithms"},{"key":"21_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/978-3-642-03685-9_24","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S. Pandit","year":"2009","unstructured":"Pandit, S., Pemmaraju, S., Varadarajan, K.: Approximation algorithms for domatic partition. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. LNCS, vol.\u00a05687, pp. 312\u2013325. Springer, Heidelberg (2009)"},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"Varadarajan, K.: Weighted geometric set cover via quasi-uniform sampling. In: STOC 2010, pp. 641\u2013648 (2010)","DOI":"10.1145\/1806689.1806777"},{"key":"21_CR20","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, New York (2001)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15775-2_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,3]],"date-time":"2019-06-03T00:18:46Z","timestamp":1559521126000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15775-2_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642157745","9783642157752"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15775-2_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}