{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T02:14:19Z","timestamp":1777342459087,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540551218","type":"print"},{"value":"9783540467359","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55121-2_8","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T09:47:45Z","timestamp":1330249665000},"page":"85-96","source":"Crossref","is-referenced-by-count":18,"title":["The complexity of approximating the class Steiner tree problem"],"prefix":"10.1007","author":[{"given":"Edmund","family":"Ihler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,5]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M. Bern","year":"1989","unstructured":"Marshall Bern and Paul Plassmann. The Steiner problem with edge lengths 1 and 2. Information Processing Letters, 32:171\u2013176, 1989.","journal-title":"Information Processing Letters"},{"key":"8_CR2","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/0022-0000(85)90039-X","volume":"31","author":"H.N. Gabow","year":"1985","unstructured":"H.N. Gabow. Scaling algorithms for network problems. J. Comp. Sys. Sc., 31:148\u2013168, 1985.","journal-title":"J. Comp. Sys. Sc."},{"key":"8_CR3","unstructured":"Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979."},{"key":"8_CR4","unstructured":"Edmund Ihler. Approximation and existential second-order logic. Technical report, Institut f\u00fcr Informatik, Universit\u00e4t Freiburg, 1990."},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Edmund Ihler. Bounds on the quality of approximate solutions to the Group Steiner Problem. In Graph-Theoretic Concepts in Computer Science,WG90, volume 484 of Lecture Notes in Computer Science, pages 109\u2013118. Springer, 1991.","DOI":"10.1007\/3-540-53832-1_36"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Edmund Ihler, Gabriele Reich, and Peter Widmayer. On shortest networks for classes of points in the plane. Technical report, Institut f\u00fcr Informatik, Universit\u00e4t Freiburg, 1991.","DOI":"10.1007\/3-540-54891-2_8"},{"key":"8_CR7","unstructured":"Richard W. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85\u2013103. Plenum Press, 1974."},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF00288961","volume":"15","author":"L. Kou","year":"1981","unstructured":"L. Kou, G. Markowsky, and L. Berman. A fast algorithm for Steiner trees. Acta Informatica, 15:141\u2013145, 1981.","journal-title":"Acta Informatica"},{"key":"8_CR9","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0020-0190(88)90066-X","volume":"27","author":"K. Mehlhorn","year":"1988","unstructured":"Kurt Mehlhorn. A faster approximation algorithm for the Steiner problem in graphs. Information Processing Letters, 27:125\u2013128, 1988.","journal-title":"Information Processing Letters"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Alessandro Panconesi and Desh Ranjan. Quantifiers and approximation. In Proc. 22th Annual ACM Symp. on Theory of Computing, pages 446\u2013456, 1990.","DOI":"10.1145\/100216.100275"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. In Proc. 20th Annual ACM Symp. on Theory of Computing, pages 229\u2013234, 1988.","DOI":"10.1145\/62212.62233"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Gabriele Reich and Peter Widmayer. Beyond Steiner's problem: A VLSI oriented generalization. In Graph-Theoretic Concepts in Computer Science,WG89, volume 411 of Lecture Notes in Computer Science. Springer, 1990.","DOI":"10.1007\/3-540-52292-1_14"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55121-2_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:57:42Z","timestamp":1605646662000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55121-2_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540551218","9783540467359"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-55121-2_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992]]}}}