{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:31:32Z","timestamp":1725543092191},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540369257"},{"type":"electronic","value":"9783540369264"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11809678_47","type":"book-chapter","created":{"date-parts":[[2006,8,15]],"date-time":"2006-08-15T09:41:33Z","timestamp":1155634893000},"page":"449-458","source":"Crossref","is-referenced-by-count":0,"title":["MAX-SNP Hardness and Approximation of Selected-Internal Steiner Trees"],"prefix":"10.1007","author":[{"given":"Sun-Yuan","family":"Hsieh","sequence":"first","affiliation":[]},{"given":"Shih-Cheng","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"47_CR1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: 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"},{"key":"47_CR2","volume-title":"Complexity and Approximation-Combinatorial Optimization Problems and Their Approximability Properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamelai, A., Protasi, M.: Complexity and Approximation-Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin (1999)"},{"issue":"4","key":"47_CR3","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); 5Zelikovsky, On wirelength estimations for row-based placement","journal-title":"Information Processing Letters"},{"key":"47_CR4","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":"47_CR5","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"doi-asserted-by":"crossref","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); 5 Information Processing Letters, vol. 84(2), pp. 103\u2013107","key":"47_CR6","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"47_CR7","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation and complexity classes. Journal of Computer and System Science\u00a043, 770\u2013779 (1991)","journal-title":"Journal of Computer and System Science"},{"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)","key":"47_CR8"},{"key":"47_CR9","volume-title":"Introduction to Graph Theory","author":"D.B. West","year":"2001","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River (2001)","edition":"2"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11809678_47.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T10:38:25Z","timestamp":1683542305000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11809678_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540369257","9783540369264"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/11809678_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}