{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:21Z","timestamp":1759638081849,"version":"3.40.3"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319182629"},{"type":"electronic","value":"9783319182636"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-18263-6_12","type":"book-chapter","created":{"date-parts":[[2015,4,22]],"date-time":"2015-04-22T14:41:38Z","timestamp":1429713698000},"page":"132-143","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Linear-Time Approximation Algorithms for Unit Disk Graphs"],"prefix":"10.1007","author":[{"given":"Guilherme D.","family":"da Fonseca","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vin\u00edcius G. Pereira","family":"de S\u00e1","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Celina M. H.","family":"de Figueiredo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,23]]},"reference":[{"key":"12_CR1","volume-title":"Combinatorial and Computational Geometry","author":"PK Agarwal","year":"2005","unstructured":"Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Geometric approximation via coresets. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Combinatorial and Computational Geometry. Cambridge University Press, Cambridge (2005)"},{"issue":"4","key":"12_CR2","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1038\/scientificamerican1077-108","volume":"237","author":"K Appel","year":"1977","unstructured":"Appel, K., Haken, W.: Solution of the four color map problem. Sci. Am. 237(4), 108\u2013121 (1977)","journal-title":"Sci. Am."},{"issue":"6","key":"12_CR3","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0020-0190(77)90070-9","volume":"6","author":"J Bentley","year":"1977","unstructured":"Bentley, J., Stanat, D., Williams Jr, E.H.: The complexity of finding fixed-radius near neighbors. Inf. Process. Lett. 6(6), 209\u2013212 (1977)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20132","key":"12_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","volume":"9","author":"H Breu","year":"1998","unstructured":"Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Comput. Geom. 9(1\u20132), 3\u201324 (1998)","journal-title":"Comput. Geom."},{"key":"12_CR5","first-page":"70","volume":"540\u2013541","author":"GD da Fonseca","year":"2014","unstructured":"da Fonseca, G.D., de Figueiredo, C.M.H., S\u00e1, V.G.P., Machado, R.C.S.: Efficient sub-5 approximations for minimum dominating sets in unit disk graphs. WAOA 2012, Theor. Comput. Sci. 540\u2013541, 70\u201381 (2014)","journal-title":"WAOA 2012, Theor. Comput. Sci."},{"issue":"23","key":"12_CR6","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1142\/S021819591350009X","volume":"6","author":"M De","year":"2013","unstructured":"De, M., Das, G., Carmi, P., Nandy, S.: Approximation algorithms for a variant of discrete piercing set problem for unit disks. Int. J. Comput. Geom. Appl. 6(23), 461\u2013477 (2013)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"1","key":"12_CR7","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130\u2013136 (1985)","journal-title":"J. ACM"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"HB Hunt III","year":"1998","unstructured":"Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithms 26, 238\u2013274 (1998)","journal-title":"J. Algorithms"},{"key":"12_CR9","unstructured":"Jallu, R.K., Prasad, P.R., Das, G.K.: Minimum dominating set for a point set in $$\\mathbb{R}^2$$. preprint, arXiv:1312.7243 (2014)"},{"issue":"2","key":"12_CR10","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"MV Marathe","year":"1995","unstructured":"Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple heuristics for unit disk graphs. Networks 25(2), 59\u201368 (1995)","journal-title":"Networks"},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/11561071_41","volume-title":"Algorithms \u2013 ESA 2005","author":"D Marx","year":"2005","unstructured":"Marx, D.: Efficient approximation schemes for geometric problems? In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 448\u2013459. Springer, Heidelberg (2005)"},{"key":"12_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-540-46515-7_16","volume-title":"Discrete and Computational Geometry","author":"T Matsui","year":"2000","unstructured":"Matsui, T.: Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs. In: Akiyama, J., Kano, M., Urabe, M. (eds.) JCDCG 1998. LNCS, vol. 1763, pp. 194\u2013200. Springer, Heidelberg (2000)"},{"issue":"4","key":"12_CR13","doi-asserted-by":"publisher","first-page":"49: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 Trans. Algorithms 4(4), 49:1\u201349:17 (2008)","journal-title":"ACM Trans. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-18263-6_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T10:20:54Z","timestamp":1675851654000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-18263-6_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319182629","9783319182636"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-18263-6_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"23 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}