{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T19:42:50Z","timestamp":1769974970070,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642219306","type":"print"},{"value":"9783642219313","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-21931-3_12","type":"book-chapter","created":{"date-parts":[[2011,6,17]],"date-time":"2011-06-17T18:11:35Z","timestamp":1308334295000},"page":"141-151","source":"Crossref","is-referenced-by-count":4,"title":["An Improved Approximation Algorithm for the Terminal Steiner Tree Problem"],"prefix":"10.1007","author":[{"given":"Yen Hung","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","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":"12_CR2","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M. Bern","year":"1989","unstructured":"Bern, M., Plassmann, P.: The Steiner Tree Problem with Edge Lengths 1 and 2. Information Processing Letters\u00a032, 171\u2013176 (1989)","journal-title":"Information Processing Letters"},{"key":"12_CR3","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1137\/S0097539795281086","volume":"26","author":"A. Borchers","year":"1997","unstructured":"Borchers, A., Du, D.Z.: The k-Steiner Ratio in Graphs. SIAM Journal on Computing\u00a026, 857\u2013869 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/274535.274536","volume-title":"Proceedings of the 1998 International Symposium on Physical Design (ISPD 1998)","author":"A. Caldwell","year":"1998","unstructured":"Caldwell, A., Kahng, A., Mantik, S., Markov, I., Zelikovsky, A.: On Wirelength Estimations for Row-Based Placement. In: Proceedings of the 1998 International Symposium on Physical Design (ISPD 1998), pp. 4\u201311. ACM, Monterey (1998)"},{"key":"12_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/3-540-45071-8_14","volume-title":"Computing and Combinatorics","author":"Y.H. Chen","year":"2003","unstructured":"Chen, Y.H., Lu, C.L., Tang, C.Y.: On the Full and Bottleneck Full Steiner Tree Problems. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol.\u00a02697, pp. 122\u2013129. Springer, Heidelberg (2003)"},{"key":"12_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0255-1","volume-title":"Steiner Tree in Industry","author":"X. Cheng","year":"2001","unstructured":"Cheng, X., Du, D.Z.: Steiner Tree in Industry. Kluwer Academic Publishers, Dordrecht (2001)"},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.ipl.2003.09.014","volume":"89","author":"D.E. Drake","year":"2004","unstructured":"Drake, D.E., Hougardy, S.: On Approximation Algorithms for the Terminal Steiner Tree Problem. Information Processing Letters\u00a089, 15\u201318 (2004)","journal-title":"Information Processing Letters"},{"key":"12_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3171-2","volume-title":"Advances in Steiner Tree","author":"D.Z. Du","year":"2000","unstructured":"Du, D.Z., Smith, J.M., Rubinstein, J.H.: Advances in Steiner Tree. Kluwer Academic Publishers, Dordrecht (2000)"},{"key":"12_CR9","doi-asserted-by":"publisher","DOI":"10.1142\/6729","volume-title":"Steiner Tree Problems in Computer Communication Networks","author":"D.Z. Du","year":"2008","unstructured":"Du, D.Z., Hu, X.: Steiner Tree Problems in Computer Communication Networks. World Scientific Publishing Company, Singapore (2008)"},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/S0020-0190(03)00285-0","volume":"87","author":"B. Fuchs","year":"2003","unstructured":"Fuchs, B.: A Note on the Terminal Steiner Tree Problem. Information Processing Letters\u00a087, 219\u2013220 (2003)","journal-title":"Information Processing Letters"},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"M.R. Garey","year":"1997","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: The Complexity of Computing Steiner Minimal Trees. SIAM Journal of Applied Mathematics\u00a032, 835\u2013859 (1997)","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"12_CR12","volume-title":"Fundamentals of Molecular Evolution","author":"D. Graur","year":"2000","unstructured":"Graur, D., Li, W.H.: Fundamentals of Molecular Evolution, 2nd edn. Sinauer Publishers, Sunderland (2000)","edition":"2"},{"key":"12_CR13","first-page":"448","volume-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999)","author":"S. Hougardy","year":"1999","unstructured":"Hougardy, S., Prommel, 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 1999), pp. 448\u2013453. ACM\/SIGACT-SIAM, Baltimore (1999)"},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s11227-007-0102-z","volume":"41","author":"S.Y. Hsieh","year":"2007","unstructured":"Hsieh, S.Y., Gao, H.M.: On the Partial Terminal Steiner Tree Problem. The Journal of Supercomputing\u00a041, 41\u201352 (2007)","journal-title":"The Journal of Supercomputing"},{"key":"12_CR15","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1016\/j.tcs.2007.05.035","volume":"381","author":"S.Y. Hsieh","year":"2007","unstructured":"Hsieh, S.Y., Yang, S.C.: Approximating the Selected-Internal Steiner Tree. Theoretical Computer Science\u00a0381, 288\u2013291 (2007)","journal-title":"Theoretical Computer Science"},{"key":"12_CR16","series-title":"Annuals of Discrete Mathematics","volume-title":"The Steiner Tree Problem","author":"F.K. Hwang","year":"1992","unstructured":"Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem. Annuals of Discrete Mathematics, vol.\u00a053. North-Holland, Elsevier, Amsterdam (1992)"},{"key":"12_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2363-2","volume-title":"On Optimal Interconnections for VLSI","author":"A.B. Kahng","year":"1995","unstructured":"Kahng, A.B., Robins, G.: On Optimal Interconnections for VLSI. Kluwer Academic Publishers, Boston (1995)"},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1023\/A:1009758919736","volume":"1","author":"M. Karpinski","year":"1997","unstructured":"Karpinski, M., Zelikovsky, A.: New Approximation Algorithms for the Steiner Tree Problems. Journal of Combinatorial Optimization\u00a01, 47\u201365 (1997)","journal-title":"Journal of Combinatorial Optimization"},{"key":"12_CR19","series-title":"Department of Ecology and Evolutionary Biology","volume-title":"Tutorial on Phylogenetic Tree Estimation","author":"J. Kim","year":"1999","unstructured":"Kim, J., Warnow, T.: Tutorial on Phylogenetic Tree Estimation. Department of Ecology and Evolutionary Biology. Yale University, New Haven (1999) (manuscript)"},{"key":"12_CR20","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S0020-0190(02)00227-2","volume":"84","author":"G.H. Lin","year":"2002","unstructured":"Lin, G.H., Xue, G.L.: On the Terminal Steiner Tree Problem. Information Processing Letters\u00a084, 103\u2013107 (2002)","journal-title":"Information Processing Letters"},{"key":"12_CR21","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S0304-3975(03)00209-3","volume":"306","author":"C.L. Lu","year":"2003","unstructured":"Lu, C.L., Tang, C.Y., Lee, R.C.T.: The Full Steiner Tree Problem. Theoretical Computer Science\u00a0306, 55\u201367 (2003)","journal-title":"Theoretical Computer Science"},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.tcs.2007.08.001","volume":"389","author":"F.V. Martineza","year":"2007","unstructured":"Martineza, F.V., Pinab, J.C.D., Soares, J.: Algorithm for Terminal Steiner Trees. Theoretical Computer Science\u00a0389, 133\u2013142 (2007)","journal-title":"Theoretical Computer Science"},{"key":"12_CR23","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1006\/jagm.2000.1086","volume":"36","author":"H.J. Prommel","year":"2000","unstructured":"Prommel, H.J., Steger, A.: A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5\/3. Journal of Algorithms\u00a036, 89\u2013101 (2000)","journal-title":"Journal of Algorithms"},{"key":"12_CR24","first-page":"770","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000)","author":"G. Robins","year":"2000","unstructured":"Robins, G., Zelikovsky, A.: Improved Steiner Tree Approximation in Graphs. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 770\u2013779. ACM\/SIGACT-SIAM, San Francisco (2000)"},{"key":"12_CR25","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G. Robins","year":"2005","unstructured":"Robins, G., Zelikovsky, A.: Tighter Bounds for Graph Steiner Tree Approximation. SIAM Journal on Discrete Mathematics\u00a019, 122\u2013134 (2005)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"12_CR26","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":"12_CR27","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0020-0190(93)90201-J","volume":"46","author":"A. Zelikovsky","year":"1993","unstructured":"Zelikovsky, A.: A Faster Approximation Algorithm for the Steiner Tree Problem in Graphs. Information Processing Letters\u00a046, 79\u201383 (1993)","journal-title":"Information Processing Letters"},{"key":"12_CR28","unstructured":"Zelikovsky, A.: Better Approximation Bounds for the Network and Euclidean Steiner Tree Problems. Technical report CS-96-06, University of Virginia (1996)"}],"container-title":["Lecture Notes in Computer Science","Computational Science and Its Applications - ICCSA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21931-3_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T12:23:46Z","timestamp":1686140626000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21931-3_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642219306","9783642219313"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21931-3_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}