{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:02:12Z","timestamp":1775815332479,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540241324","type":"print"},{"value":"9783540305590","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30559-0_18","type":"book-chapter","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T19:01:42Z","timestamp":1278097302000},"page":"214-221","source":"Crossref","is-referenced-by-count":38,"title":["A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs"],"prefix":"10.1007","author":[{"given":"Tim","family":"Nieberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johann","family":"Hurink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Walter","family":"Kern","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"18_CR1","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)","journal-title":"Journal of the ACM"},{"issue":"1-2","key":"18_CR2","doi-asserted-by":"crossref","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. Computational Geometry. Theory and Applications\u00a09(1-2), 3\u201324 (1998)","journal-title":"Computational Geometry. Theory and Applications"},{"key":"18_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. Journal of Algorithms\u00a046, 178\u2013189 (2003)","journal-title":"Journal of Algorithms"},{"key":"18_CR4","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, 202\u2013208 (2003)","journal-title":"Networks"},{"key":"18_CR5","unstructured":"Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric graphs. In: Proceedings of the 12th ACM-SIAM symposium on discrete algorithms (SODA 2001), Washington, DC, pp. 671\u2013679 (2001)"},{"key":"18_CR6","volume-title":"Concrete Mathematics","author":"R.L. Graham","year":"1998","unstructured":"Graham, R.L., Knuth, D.E., Potashnik, O.: Concrete Mathematics, 2nd edn. Addison- Wesley, London (1998)","edition":"2"},{"issue":"1","key":"18_CR7","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. Journal of the ACM\u00a032(1), 130\u2013136 (1985)","journal-title":"Journal of the ACM"},{"key":"18_CR8","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"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R., Zollinger, A.: Ad-hoc networks beyond unit disk graphs. In: 1st ACM DIALM-POMC Joint Workshop on Foundations of Distributed Computing, San Diego, USA (2003)","DOI":"10.1145\/941079.941089"},{"key":"18_CR10","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":"18_CR11","volume-title":"Ambient Intelligence: Impact on Embedded System Design","author":"T. Nieberg","year":"2003","unstructured":"Nieberg, T., Dulman, S., Havinga, P., Hoessel, L.v., Wu, J.: Collaborative algorithms for communication in wireless sensor networks. In: Basten, T., Geilen, M., De Groot, H. (eds.) Ambient Intelligence: Impact on Embedded System Design. Kluwer Academic Publishers, Dordrecht (2003)"},{"key":"18_CR12","unstructured":"Raghavan, V., Spinrad, J.: Robust algorithms for restricted domains. In: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pp. 460\u2013467, Society for Industrial and Applied Mathematics (2001)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30559-0_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:29:59Z","timestamp":1620012599000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30559-0_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241324","9783540305590"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30559-0_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}