{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T00:56:22Z","timestamp":1743123382691,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642020254"},{"type":"electronic","value":"9783642020261"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02026-1_4","type":"book-chapter","created":{"date-parts":[[2009,6,17]],"date-time":"2009-06-17T16:31:23Z","timestamp":1245256283000},"page":"36-48","source":"Crossref","is-referenced-by-count":10,"title":["A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs"],"prefix":"10.1007","author":[{"given":"Xianyue","family":"Li","sequence":"first","affiliation":[]},{"given":"Xiao-Hua","family":"Xu","sequence":"additional","affiliation":[]},{"given":"Feng","family":"Zou","sequence":"additional","affiliation":[]},{"given":"Hongwei","family":"Du","sequence":"additional","affiliation":[]},{"given":"Pengjun","family":"Wan","sequence":"additional","affiliation":[]},{"given":"Yuexuan","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Weili","family":"Wu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_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 (Connect) 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)"},{"key":"4_CR2","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 Algorithm for NP-Complete Problems on Planar Graphs. Journal of the ACM\u00a041, 153\u2013180 (1994)","journal-title":"Journal of the ACM"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Berman, P.: Personal Communciation (1991)","DOI":"10.3817\/0391087059"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1006\/jagm.1994.1041","volume":"17","author":"P. Berman","year":"1994","unstructured":"Berman, P., Ramaiyer, V.: Improved Approximations for the Steiner Tree Problem. Journal of Algorithms\u00a017, 381\u2013408 (1994)","journal-title":"Journal of Algorithms"},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0304-3975(00)00182-1","volume":"262","author":"D. Chen","year":"2001","unstructured":"Chen, D., Du, D.Z., Hu, X.D., Lin, G.H., Wang, L., Xue, G.: Approximation for Steienr Trees with Minimum Number of Steiner Points. Theoretical Computer Science\u00a0262, 83\u201399 (2001)","journal-title":"Theoretical Computer Science"},{"key":"4_CR6","unstructured":"Dai, D., Yu, C.: A 5-Approximation Algorithm for Minimum Weighted Dominating Set in Unit Disk Graph. Theoretical Computer Science (to appear)"},{"key":"4_CR7","series-title":"A Guide to the Theory of NP-completeness","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-completeness. Freeman, New York (1979)"},{"key":"4_CR8","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 of Approximating Node Weighted Steiner Tree and Connected Dominating Sets. Information and Computation\u00a0150, 57\u201374 (1999)","journal-title":"Information and Computation"},{"key":"4_CR9","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, 130\u2013136 (1985)","journal-title":"Journal of the ACM"},{"key":"4_CR10","unstructured":"Hougardy, S., Pr\u00f6mel, H.J.: A 1.598-Approximation Algorithm for the Steiner Problem in Graphs. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 448\u2013453 (1999)"},{"key":"4_CR11","unstructured":"Huang, Y., Gao, X., Zhang, Z., Wu, W.: A Better Constant-Factor Approximation for Weighted Dominating Set in Unit Disk Graph. Jounral of Combibatorial Optimization (to appear)"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/net.3230220105","volume":"22","author":"F.K. Hwang","year":"1992","unstructured":"Hwang, F.K., Richards, D.S.: Steiner tree problems. Networks\u00a022, 55\u201389 (1992)","journal-title":"Networks"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1006\/jagm.1995.1029","volume":"19","author":"P. Klein","year":"1995","unstructured":"Klein, P., Ravi, R.: A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees. Journal of Algorithms\u00a019, 104\u2013115 (1995)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"4_CR14","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF00288961","volume":"15","author":"L.T. Kou","year":"1981","unstructured":"Kou, L.T., Markowsky, G., Berman, L.: A Fast Algorithm for Steiner Trees. Acta Informatica\u00a015(2), 141\u2013145 (1981)","journal-title":"Acta Informatica"},{"key":"4_CR15","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, 329\u2013343 (1982)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Robins, G., Salowe, J.S.: On the Maximum Degree of Minimum Spanning Trees. In: Proceedings of the ACM Symposium on Computational Geometry, pp. 250\u2013258 (1994)","DOI":"10.1145\/177424.177978"},{"key":"4_CR17","unstructured":"Robins, G., Zelikovski, A.: Improved Steiner Tree Approximation in Graphs. In: Proc. of the 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 770\u2013779 (2000)"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1002\/(SICI)1097-0037(199612)28:4<187::AID-NET3>3.0.CO;2-H","volume":"28","author":"L. Wang","year":"1996","unstructured":"Wang, L., Jiang, T.: An Approximation Scheme for Some Steiner Tree Problem in the Plane. Networks\u00a028, 187\u2013193 (1996)","journal-title":"Networks"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2005.08.037","volume":"352","author":"W. Wu","year":"2006","unstructured":"Wu, W., Du, H., Jia, X., Li, Y., Huang, S.C.H.: Minimum Connected Dominating Sets and Maximal Independent Sets in Unit Disk Graphs. Theor. Comput. Sci.\u00a0352, 1\u20137 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR20","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A. Zelikovsky","year":"1993","unstructured":"Zelikovsky, A.: An 11\/6 Approximation Algorithm for the Network Steiner Problem. Algorithmica\u00a09, 463\u2013470 (1993)","journal-title":"Algorithmica"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-540-85097-7_26","volume-title":"Combinatorial Optimization and Applications","author":"F. Zou","year":"2008","unstructured":"Zou, F., Li, X., Kim, D., Wu, W.: Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs. In: Yang, B., Du, D.-Z., Wang, C.A. (eds.) COCOA 2008. LNCS, vol.\u00a05165, pp. 278\u2013285. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02026-1_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T03:54:13Z","timestamp":1714622053000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-02026-1_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642020254","9783642020261"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02026-1_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}