{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:33:21Z","timestamp":1759638801353},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540850960"},{"type":"electronic","value":"9783540850977"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85097-7_26","type":"book-chapter","created":{"date-parts":[[2008,8,19]],"date-time":"2008-08-19T03:18:26Z","timestamp":1219115906000},"page":"278-285","source":"Crossref","is-referenced-by-count":7,"title":["Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs"],"prefix":"10.1007","author":[{"given":"Feng","family":"Zou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xianyue","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donghyun","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weili","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1002\/net.3230100207","volume":"10","author":"Y.P. Aneja","year":"1980","unstructured":"Aneja, Y.P.: An integer linear programming approach to the Steiner problem in graphs. Networks\u00a010, 167\u2013178 (1980)","journal-title":"Networks"},{"key":"26_CR2","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1002\/net.3230140112","volume":"14","author":"J.E. Beasley","year":"1984","unstructured":"Beasley, J.E.: An algorithm for the Steiner problem in graphs. Networks\u00a014, 147\u2013159 (1984)","journal-title":"Networks"},{"key":"26_CR3","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":"26_CR4","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 Steiner tree with minimum number of Steiner points. Theoretical Computer Science\u00a0262, 83\u201399 (2001)","journal-title":"Theoretical Computer Science"},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of lnn for approximating set cover. J. ACM\u00a045, 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"26_CR6","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability:A Guide to the Theory of NP-Completeness. Freeman, San Fransico (1978)"},{"key":"26_CR7","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, 57\u201374 (1999)","journal-title":"Information and Computation"},{"key":"26_CR8","unstructured":"Hougardy, S., Pr\u00f6mel, H.J.: A 1.598 Approximation Algorithm for the Steiner Problem in Graphs. SODA, 448\u2013453 (1998)"},{"key":"26_CR9","unstructured":"Huang, Y., Gao, X., Zhang, Z., Wu, W.: A Better Constant-Factor Approximation for Weighted Dominating Set in Unit Disk Graph (preprint)"},{"key":"26_CR10","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"},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"Kou, L.T., Markowsky, G., Berman, L.: A Fast Algorithm for Steiner Trees, pp. 141\u2013145 (1981)","DOI":"10.1007\/BF00288961"},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s10898-005-8466-1","volume":"35","author":"M. Min","year":"2006","unstructured":"Min, M., Du, H., Jia, X., Huang, C.X., Huang, S.C.H., Wu, W.: Improving Construction for Connected Dominating Set with Steiner Tree in Wireless Sensor Networks. Journal of Global Optimizatio\u00a035, 111\u2013119 (2006)","journal-title":"Journal of Global Optimizatio"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Moss, A., Rabani, Y.: Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems. In: STOC (2001)","DOI":"10.1145\/380752.380826"},{"key":"26_CR14","unstructured":"Robins, G., Zelikovski, A.: Improved Steiner Tree Approximation in Graphs. In: Proc. of 11th. ACM-SIAM Symposium on Discrete. Algorithms, pp. 770\u2013779 (2000)"},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/net.3230170102","volume":"17","author":"A. Segev","year":"1987","unstructured":"Segev, A.: The node-weighted steiner tree problem. Networks\u00a017, 1\u201317 (1987)","journal-title":"Networks"},{"key":"26_CR16","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1002\/net.3230120309","volume":"12","author":"M.L. Shore","year":"1982","unstructured":"Shore, M.L., Foulds, L.R., Gibbons, R.B.: An algorithm for the Steiner problem in graphs. Networks\u00a012, 323\u2013333 (1982)","journal-title":"Networks"},{"key":"26_CR17","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"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85097-7_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:21:54Z","timestamp":1606166514000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85097-7_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540850960","9783540850977"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85097-7_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}