{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T18:06:22Z","timestamp":1772042782304,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540380443","type":"print"},{"value":"9783540380450","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11830924_3","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T08:33:54Z","timestamp":1156494834000},"page":"3-14","source":"Crossref","is-referenced-by-count":103,"title":["Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs"],"prefix":"10.1007","author":[{"given":"Christoph","family":"Amb\u00fchl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Erlebach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mat\u00fa\u0161","family":"Mihal\u00e1k","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Nunkesser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Alzoubi, K., Wan, P.-J., Frieder, O.: Message-optimal connected dominating sets in mobile ad hoc networks. In: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2002), pp. 157\u2013164 (2002)","DOI":"10.1145\/513800.513820"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Amb\u00fchl, C., Erlebach, T., Mihal\u2019\u00e1k, M., Nunkesser, M.: Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. Research Report CS-06-008, Department of Computer Science, University of Leicester (June 2006)","DOI":"10.1007\/11830924_3"},{"issue":"1","key":"3_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM\u00a041(1), 153\u2013180 (1994); Extended abstract published in the proceedings of FOCS 1983, pp. 265\u2013273 (1983)","journal-title":"Journal of the ACM"},{"issue":"4","key":"3_CR4","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 & Computational Geometry\u00a014(4), 463\u2013479 (1995)","journal-title":"Discrete & Computational Geometry"},{"issue":"2","key":"3_CR5","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1023\/B:MONE.0000013622.63511.57","volume":"9","author":"G. Calinescu","year":"2004","unstructured":"Calinescu, G., Mandoiu, I., Wan, P.-J., Zelikovsky, A.: Selecting forwarding neighbors in wireless ad hoc networks. Mobile Networks and Applications\u00a09(2), 101\u2013111 (2004)","journal-title":"Mobile Networks and Applications"},{"issue":"4","key":"3_CR6","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1002\/net.10097","volume":"42","author":"X. Cheng","year":"2003","unstructured":"Cheng, X., Huang, X., Li, D., Wu, W., Du, D.-Z.: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks\u00a042(4), 202\u2013208 (2003)","journal-title":"Networks"},{"key":"3_CR7","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, 165\u2013177 (1990)","journal-title":"Discrete Mathematics"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC 1996), pp. 314\u2013318 (1996)","DOI":"10.1145\/237814.237977"},{"key":"3_CR9","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.\u00a0H. Freeman and Company, New York (1979)"},{"issue":"1","key":"3_CR10","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1006\/inco.1998.2754","volume":"150","author":"S. Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Improved methods for approximating node weighted Steiner trees and connected dominating sets. Information and Computation\u00a0150(1), 57\u201374 (1999)","journal-title":"Information and Computation"},{"issue":"1","key":"3_CR11","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","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. Journal of the ACM\u00a032(1), 130\u2013136 (1985)","journal-title":"Journal of the ACM"},{"issue":"2","key":"3_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. Journal of Algorithms\u00a026(2), 238\u2013274 (1998)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"3_CR13","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM Journal on Computing\u00a011(2), 329\u2013343 (1982)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR14","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":"3_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/11604686_31","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"E.J. Leeuwen van","year":"2005","unstructured":"van Leeuwen, E.J.: Approximation algorithms for unit disk graphs. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 351\u2013361. Springer, Heidelberg (2005)"},{"key":"3_CR16","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Wang, Y., Li, X.-Y.: Distributed low-cost backbone formation for wireless ad hoc networks. In: Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2005), pp. 2\u201313 (2005)","DOI":"10.1145\/1062689.1062692"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11830924_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:18:32Z","timestamp":1605626312000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11830924_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540380443","9783540380450"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11830924_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}