{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:18:41Z","timestamp":1760440721696},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540787723"},{"type":"electronic","value":"9783540787730"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-78773-0_64","type":"book-chapter","created":{"date-parts":[[2008,4,3]],"date-time":"2008-04-03T08:38:35Z","timestamp":1207211915000},"page":"747-758","source":"Crossref","is-referenced-by-count":12,"title":["Domination in Geometric Intersection Graphs"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Erlebach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-2","key":"64_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P. Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theoret. Comput. Sci.\u00a0237(1-2), 123\u2013134 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"64_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/11830924_3","volume-title":"Proc. APPROX-RANDOM 2006","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., Zwick, U. (eds.) Proc. APPROX-RANDOM 2006. LNCS, vol.\u00a04110, pp. 3\u201314. Springer-Verlag, Berlin\/Heidelberg (2006)"},{"issue":"1","key":"64_CR3","first-page":"153","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation Algorithms for NP-Complete Problems on Planar Graphs. J.\u00a0ACM\u00a041(1), 153\u2013180 (1994)","journal-title":"J.\u00a0ACM"},{"issue":"2","key":"64_CR4","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R. Bar-Yehuda","year":"1981","unstructured":"Bar-Yehuda, R., Even, S.: A Linear-Time Approximation Algorithm for the Weighted Vertex Cover Problem. J.\u00a0Algorithms\u00a02(2), 198\u2013203 (1981)","journal-title":"J.\u00a0Algorithms"},{"issue":"4","key":"64_CR5","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H. Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost Optimal Set Covers in Finite VC-Dimension. Discrete Comput. Geometry\u00a014(4), 463\u2013479 (1995)","journal-title":"Discrete Comput. Geometry"},{"issue":"2","key":"64_CR6","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"},{"issue":"6","key":"64_CR7","doi-asserted-by":"publisher","first-page":"1671","DOI":"10.1137\/S0097539792238431","volume":"27","author":"M.-S. Chang","year":"1998","unstructured":"Chang, M.-S.: Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs. SIAM J. Comput.\u00a027(6), 1671\u20131694 (1998)","journal-title":"SIAM J. Comput."},{"key":"64_CR8","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-Verlag, Berlin\/Heidelberg (2004)"},{"issue":"1","key":"64_CR9","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1137\/050629276","volume":"21","author":"M. Chleb\u00edk","year":"2007","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: The Complexity of Combinatorial Optimization Problems on d-Dimensional Boxes. SIAM J. Discrete Math.\u00a021(1), 158\u2013169 (2007)","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20133","key":"64_CR10","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 Math.\u00a086(1\u20133), 165\u2013177 (1990)","journal-title":"Discrete Math."},{"issue":"1","key":"64_CR11","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00454-006-1273-8","volume":"37","author":"K.L. Clarkson","year":"2007","unstructured":"Clarkson, K.L., Varadarajan, K.R.: Improved Approximation Algorithms for Geometric Set Cover. Discrete Comput. Geometry\u00a037(1), 43\u201358 (2007)","journal-title":"Discrete Comput. Geometry"},{"issue":"2","key":"64_CR12","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/PL00009494","volume":"23","author":"A. Efrat","year":"2000","unstructured":"Efrat, A., Sharir, M.: The Complexity of the Union of Fat Objects in the Plane. Discrete Comput. Geometry\u00a023(2), 171\u2013189 (2000)","journal-title":"Discrete Comput. Geometry"},{"issue":"6","key":"64_CR13","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.\u00a0Comput.\u00a034(6), 1302\u20131323 (2005)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"2","key":"64_CR14","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1016\/j.ipl.2005.03.010","volume":"95","author":"G. Even","year":"2005","unstructured":"Even, G., Rawitz, D., Sharar, S.: Hitting Sets when the VC-Dimension is Small. Inform. Process. Lett.\u00a095(2), 358\u2013362 (2005)","journal-title":"Inform. Process. Lett."},{"issue":"4","key":"64_CR15","first-page":"634","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A Threshold of ln n for Approximating Set Cover. J.\u00a0ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"J.\u00a0ACM"},{"issue":"3","key":"64_CR16","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"D.S. Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Approximation Algorithms for the Set Covering and Vertex Cover Problems. SIAM J.\u00a0Comput.\u00a011(3), 555\u2013556 (1982)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"1","key":"64_CR17","first-page":"130","volume":"32","author":"D.S. Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI. J.\u00a0ACM\u00a032(1), 130\u2013136 (1985)","journal-title":"J.\u00a0ACM"},{"issue":"2","key":"64_CR18","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"D.B. Hunt III","year":"1998","unstructured":"Hunt III, D.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"},{"key":"64_CR19","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF02187683","volume":"1","author":"K. Kedem","year":"1986","unstructured":"Kedem, K., Livne, R., Pach, J., Sharir, M.: On the Union of Jordan Regions and Collision-Free Translational Motion Amidst Polygonal Obstacles. Discrete Comput. Geometry\u00a01, 59\u201370 (1986)","journal-title":"Discrete Comput. Geometry"},{"key":"64_CR20","doi-asserted-by":"crossref","unstructured":"Kim, S.-J., Kostochka, A., Nakprasit, K.: On the Chromatic Number of Intersection Graphs of Convex Sets in the Plane. Electr. J. Combinatorics\u00a011, #R52 (2004)","DOI":"10.37236\/1805"},{"key":"64_CR21","first-page":"141","volume":"88","author":"P. Koebe","year":"1936","unstructured":"Koebe, P.: Kontaktprobleme der konformen Abbildung. Ber. Ver. S\u00e4chs. Ak. Wiss. Leipzig, Math.-Phys. Kl.\u00a088, 141\u2013164 (1936)","journal-title":"Ber. Ver. S\u00e4chs. Ak. Wiss. Leipzig, Math.-Phys. Kl."},{"key":"64_CR22","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"M.V. 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\u00a025, 59\u201368 (1995)","journal-title":"Networks"},{"key":"64_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/11847250_14","volume-title":"Parameterized and Exact Computation","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized Complexity of Independence and Domination on Geometric Graphs. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 154\u2013165. Springer-Verlag, Berlin\/Heidelberg (2006)"},{"issue":"1","key":"64_CR24","first-page":"1","volume":"44","author":"G.L. Miller","year":"1997","unstructured":"Miller, G.L., Teng, S.-H., Thurston, W., Vavasis, S.A.: Separators for Sphere-Packings and Nearest Neighbor Graphs. J.\u00a0ACM\u00a044(1), 1\u201329 (1997)","journal-title":"J.\u00a0ACM"},{"key":"64_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/11671411_23","volume-title":"Approximation and Online Algorithms","author":"T. Nieberg","year":"2006","unstructured":"Nieberg, T., Hurink, J.L.: A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol.\u00a03879, pp. 296\u2013306. Springer-Verlag, Berlin\/Heidelberg (2006)"},{"key":"64_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/11785293_30","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"E.J. Leeuwen van","year":"2006","unstructured":"van Leeuwen, E.J.: Better Approximation Schemes for Disk Graphs. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol.\u00a04059, pp. 316\u2013327. Springer-Verlag, Berlin\/Heidelberg (2006)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2008: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78773-0_64","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,3]],"date-time":"2020-05-03T18:33:48Z","timestamp":1588530828000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78773-0_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540787723","9783540787730"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78773-0_64","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}