{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:34:09Z","timestamp":1725514449157},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540725039"},{"type":"electronic","value":"9783540725046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72504-6_25","type":"book-chapter","created":{"date-parts":[[2007,7,22]],"date-time":"2007-07-22T07:36:39Z","timestamp":1185089799000},"page":"274-283","source":"Crossref","is-referenced-by-count":3,"title":["On the Internal Steiner Tree Problem"],"prefix":"10.1007","author":[{"given":"Sun-Yuan","family":"Hsieh","sequence":"first","affiliation":[]},{"given":"Huang-Ming","family":"Gao","sequence":"additional","affiliation":[]},{"given":"Shih-Cheng","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., et al.: Proof verification and the hardness of approximation problems. Journal of the Association for Computing Machinery\u00a045, 501\u2013555 (1998)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"4","key":"25_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 problem with edge lengths 1 and 2. Information Processing Letters\u00a032(4), 171\u2013176 (1989)","journal-title":"Information Processing Letters"},{"key":"25_CR3","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 Publishers, Dordrecht (2001)"},{"key":"25_CR4","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., et al.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"25_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 Publishers, Dordrecht (2000)"},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"M. Garey","year":"1977","unstructured":"Garey, M., Graham, R., Johnson, D.: The complexity of computing Steiner minimal trees. SIAM Journal on Applied Mathematics\u00a032, 835\u2013859 (1977)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"25_CR7","doi-asserted-by":"publisher","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 Journal on Applied Mathematics\u00a032, 826\u2013834 (1977)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"25_CR8","series-title":"Annals 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. Annals of Discrete Mathematics, vol.\u00a053. Elsevier Science Publishers, Amsterdam (1992)"},{"key":"25_CR9","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. Karp","year":"1972","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. In: Proceedings of the 20th ACM Symposium on Theory of Computing, pp. 229\u2013234 (1988)","DOI":"10.1145\/62212.62233"},{"key":"25_CR11","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. 770\u2013779 (2000)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72504-6_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T10:09:16Z","timestamp":1683972556000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72504-6_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540725039","9783540725046"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72504-6_25","relation":{},"subject":[]}}