{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T17:40:21Z","timestamp":1684950021235},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,3,28]],"date-time":"2009-03-28T00:00:00Z","timestamp":1238198400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,3]]},"DOI":"10.1007\/s00453-009-9301-8","type":"journal-article","created":{"date-parts":[[2009,3,30]],"date-time":"2009-03-30T13:51:30Z","timestamp":1238421090000},"page":"333-341","source":"Crossref","is-referenced-by-count":8,"title":["A Better Constant-Factor Approximation for\u00a0Selected-Internal Steiner Minimum Tree"],"prefix":"10.1007","volume":"56","author":[{"given":"Xianyue","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feng","family":"Zou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yaochun","family":"Huang","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","published-online":{"date-parts":[[2009,3,28]]},"reference":[{"key":"9301_CR1","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1137\/S0097539795281086","volume":"26","author":"A. Borchers","year":"1997","unstructured":"Borchers, A., Du, D.Z.: The\u00a0k-Steiner ratio in graphs. SIAM J. Comput. 26, 857\u2013869 (1997)","journal-title":"SIAM J. Comput."},{"key":"9301_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0255-1","volume-title":"Steiner Trees in Industry","author":"X. Cheng","year":"2001","unstructured":"Cheng, X., Du, D.Z.: Steiner Trees in Industry. Kluwer Academic, Dordrecht (2001)"},{"key":"9301_CR3","doi-asserted-by":"crossref","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. Inf. Process. Lett. 89, 15\u201318 (2004)","journal-title":"Inf. Process. Lett."},{"key":"9301_CR4","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0166-218X(94)00045-F","volume":"60","author":"D.Z. Du","year":"1995","unstructured":"Du, D.Z.: On component-size bounded Steiner trees. Discrete Appl. Math. 60, 131\u2013140 (1995)","journal-title":"Discrete Appl. Math."},{"key":"9301_CR5","volume-title":"Advance in Steiner Tree","author":"D.Z. Du","year":"2000","unstructured":"Du, D.Z., Smith, J.M., Rubinstein, J.H.: Advance in Steiner Tree. Kluwer Academic, Dordrecht (2000)"},{"key":"9301_CR6","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0196-8858(82)80004-3","volume":"3","author":"L. Foulds","year":"1982","unstructured":"Foulds, L., Graham, R.: The Steiner problem in phylogeny is NP-complete. Adv. Appl. Math. 3, 43\u201349 (1982)","journal-title":"Adv. Appl. Math."},{"key":"9301_CR7","doi-asserted-by":"crossref","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. Inf. Process. Lett. 87, 219\u2013220 (2003)","journal-title":"Inf. Process. Lett."},{"key":"9301_CR8","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M. Garey","year":"1977","unstructured":"Garey, M., Johnson, D.: The rectilinear Steiner problem is NP-complete. SIAM J. Appl. Math. 32, 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"9301_CR9","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"M. Garey","year":"1997","unstructured":"Garey, M., Graham, R., Johnson, D.: The complexity of computing Steriner minimal tree. SIAM J. Appl. Math. 32, 835\u2013859 (1997)","journal-title":"SIAM J. Appl. Math."},{"key":"9301_CR10","volume-title":"Fundamentals of Molecular Evolution","author":"D. Graur","year":"2000","unstructured":"Graur, D., Li, W.H.: Fundamentals of Molecular Evolution, 2nd edn. Sinauer, Sunderland (2000)","edition":"2"},{"key":"9301_CR11","doi-asserted-by":"crossref","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. J. Supercomput. 41, 41\u201352 (2007)","journal-title":"J. Supercomput."},{"key":"9301_CR12","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 381, 288\u2013291 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9301_CR13","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. North-Holland, Amsterdam (1992)"},{"key":"9301_CR14","doi-asserted-by":"crossref","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, Dordrecht (1995)"},{"key":"9301_CR15","volume-title":"Paths, Flows and VLSI-Layout","author":"B. Korte","year":"1990","unstructured":"Korte, B., Pr\u00f6mel, H.J., Steger, A.: Steiner Trees in VLSI-Layouts. In: Korte, B., (eds.) Paths, Flows and VLSI-Layout. Springer, New York (1990)"},{"key":"9301_CR16","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0020-0190(02)00227-2","volume":"84","author":"G. Lin","year":"2002","unstructured":"Lin, G., Xue, G.: On the terminal Steiner tree problem. Inf. Process. Lett. 84, 103\u2013107 (2002)","journal-title":"Inf. Process. Lett."},{"key":"9301_CR17","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 306, 55\u201367 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9301_CR18","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 389, 133\u2013142 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9301_CR19","unstructured":"Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp.\u00a0770\u2013779 (2000)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9301-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9301-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9301-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T17:17:33Z","timestamp":1684948653000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9301-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,28]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["9301"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9301-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3,28]]}}}