{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T14:01:49Z","timestamp":1742392909578},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_59","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:32:38Z","timestamp":1188351158000},"page":"678-689","source":"Crossref","is-referenced-by-count":11,"title":["On the Approximability of the Steiner Tree Problem"],"prefix":"10.1007","author":[{"given":"Martin","family":"Thimm","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"key":"59_CR1","unstructured":"S. Arora, Polynomial time approximation schemes for the Euclidian TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science (1996), pp. 2\u201311."},{"key":"59_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification an hardness of approximation problems, Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (1992), pp. 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"59_CR3","doi-asserted-by":"crossref","unstructured":"P. Berman, M. Karpinski, On Some Tighter Inapproximability Results, Further Improvements, Electronic Colloquium on Computational Complexity, Report No.65 (1998)","DOI":"10.1007\/3-540-48523-6_17"},{"key":"59_CR4","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1006\/jagm.1994.1041","volume":"17","author":"P. Berman","year":"1994","unstructured":"P. Berman, V. Ramaiyer, Improved approximations for the Steiner tree problem, Journal of Algorithms 17 (1994), pp. 381\u2013408.","journal-title":"Journal of Algorithms"},{"key":"59_CR5","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M. Bern","year":"1989","unstructured":"M. Bern, P. Plassmann, The Steiner Problem with edge lengths 1 an 2, Information Processing Letters 32 (1989), pp. 171\u2013176.","journal-title":"Information Processing Letters"},{"key":"59_CR6","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"O. Gabber","year":"1981","unstructured":"O. Gabber, Z. Galil, Explicit construction of linear-sized superconcentrators, J. Comput. System Sci. 22 (1981) pp. 407\u2013420","journal-title":"J. Comput. System Sci."},{"key":"59_CR7","doi-asserted-by":"crossref","unstructured":"C. Gr\u00f6pl, S. Hougardy, T. Nierhoff, H. J. Pr\u00f6mel, Approximation algorithms for the Steiner tree problem in graphs, technical report, Humboldt-Universit\u00e4t zu Berlin, 2000.","DOI":"10.1007\/978-1-4613-0255-1_7"},{"key":"59_CR8","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Some optimal inapproximability results, Proceedings of the 28rd Annual Symposium on Theory of Computing, ACM, 1997.","DOI":"10.1145\/258533.258536"},{"key":"59_CR9","unstructured":"S. Hougardy, H. J. Pr\u00f6mel, A 1.598 approximation algorithm for the Steiner Problem in graphs, In: Proceeding of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms 1999, pp. 448\u2013453."},{"key":"59_CR10","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1023\/A:1009758919736","volume":"1","author":"M. Karpinski","year":"1997","unstructured":"M. Karpinski, A. Zelikovsky, New approximation algorithms for the Steiner tree problems, Journal of Combinatorial Optimization 1 (1997), pp. 47\u201365.","journal-title":"Journal of Combinatorial Optimization"},{"key":"59_CR11","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A. Lubotzy","year":"1988","unstructured":"A. Lubotzy, P. Philips, P. Sarnak, Ramanujan graphs, Combinatorica, 8, (1988) pp. 261\u2013277.","journal-title":"Combinatorica"},{"key":"59_CR12","first-page":"325","volume":"9","author":"G. A. Margulis","year":"1973","unstructured":"G. A. Margulis, Explicit construction of concentrators, Problemy Inf. Trans. 9 (1973), pp. 325\u2013332","journal-title":"Problemy Inf. Trans"},{"key":"59_CR13","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou, S. Vempala, On the Approximability of the Traveling Salesman Problem, Proceedings of the 32nd ACM Symposium on the theory of computing, Portland, 2000.","DOI":"10.1145\/335305.335320"},{"key":"59_CR14","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1006\/jagm.2000.1086","volume":"36","author":"H. J. Pr\u00f6mel","year":"2000","unstructured":"H. J. Pr\u00f6mel, A. Steger, A new approximation algorithm for the Steiner tree problem with perfomance ratio 5\/3, Journal of Algorithms 36 (2000), pp. 89\u2013101.","journal-title":"Journal of Algorithms"},{"key":"59_CR15","unstructured":"G. Robins, A. Zelikovsky, Improved Steiner tree approximation in graphs, In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms 2000, pp. 770\u2013779."},{"key":"59_CR16","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A. Zelikovsky","year":"1993","unstructured":"A. Zelikovsky, An 11\/6-approximation algorithm for the network Steiner problem, Algorithmica 9 (1993), pp. 463\u2013470.","journal-title":"Algorithmica"},{"key":"59_CR17","doi-asserted-by":"crossref","unstructured":"P. Sarnak, Some Applications of Modular Forms, Cambridge Tracts in Mathematics 99, Cambridge University Press, 1990","DOI":"10.1017\/CBO9780511895593"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_59","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T17:27:43Z","timestamp":1556818063000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_59","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}