{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T19:33:46Z","timestamp":1769974426056,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540626169","type":"print"},{"value":"9783540683421","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0023489","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T02:06:33Z","timestamp":1132365993000},"page":"559-570","source":"Crossref","is-referenced-by-count":16,"title":["RNC-approximation algorithms for the steiner problem"],"prefix":"10.1007","author":[{"given":"Hans J\u00fcrgen","family":"Pr\u00f6mel","sequence":"first","affiliation":[]},{"given":"Angelika","family":"Steger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"key":"46_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and hardness of approximation problems, Proc. 33rd Annual IEEE Symp. Foundations of Computer Science (1992), 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"46_CR2","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1006\/jagm.1994.1041","volume":"17","author":"P. Berman","year":"1994","unstructured":"P. Berman and V. Ramaiyer, Improved Approximations for the Steiner Tree Problem, Journal of Algorithms17 (1994), 381\u2013408.","journal-title":"Journal of Algorithms"},{"key":"46_CR3","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 and P. Plassmann, The Steiner problem with edge lengths 1 and 2, Information Processing Letters32 (1989), 171\u2013176.","journal-title":"Information Processing Letters"},{"key":"46_CR4","doi-asserted-by":"crossref","unstructured":"A. Borchers and D.-Z. Du, The k-Steiner ratio in graphs, Proc. 27th Annual ACM Symp. on the Theory of Computing (1995), 641\u2013649.","DOI":"10.1145\/225058.225282"},{"key":"46_CR5","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/0196-6774(92)90018-8","volume":"13","author":"P.M. Camerini","year":"1992","unstructured":"P.M. Camerini, G. Galbiati, and F. Maffioli, Random pseudo-polynomial algorithms for exact matroid problems, Journal of Algorithms13 (1992), 258\u2013273.","journal-title":"Journal of Algorithms"},{"key":"46_CR6","first-page":"207","volume":"12","author":"C. El-Arbi","year":"1978","unstructured":"Choukhmane El-Arbi, Une heuristique pour le probl\u00e8me de l'arbre de Steiner, R.A.I.R.O. Recherche op\u00e9rationnelle12 (1978), 207\u2013212.","journal-title":"R.A.I.R.O. Recherche op\u00e9rationnelle"},{"key":"46_CR7","doi-asserted-by":"crossref","unstructured":"D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, Proc. 19th Annual ACM Symp. on Theory of Computing (1987), 1\u20136.","DOI":"10.1145\/28395.28396"},{"key":"46_CR8","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S.E. Dreyfus","year":"1972","unstructured":"S.E. Dreyfus and R.A. Wagner, The Steiner problem in graphs, Networks1 (1972), 195\u2013207.","journal-title":"Networks"},{"key":"46_CR9","doi-asserted-by":"crossref","unstructured":"D.-Z. Du, Y.-J. Zhang and Q. Feng, On better heuristic for Euclidean Steiner minimum trees, Proc. 32nd Annual IEEE Symp. on Foundations of Computer Science (1991), 431\u2013439.","DOI":"10.1109\/SFCS.1991.185402"},{"key":"46_CR10","doi-asserted-by":"crossref","unstructured":"H.N. Gabow, Z. Galil, T.H. Spencer, Efficient implementation of graph algorithms using contraction, Proc. 25th Annual IEEE Symp. on Foundations of Computer Science (1984), 347\u2013357.","DOI":"10.1109\/SFCS.1984.715935"},{"key":"46_CR11","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/BF02579169","volume":"6","author":"H.N. Gabow","year":"1986","unstructured":"H.N. Gabow and M. Stallmann, An augmenting path algorithm for linear matroid parity, Combinatorica6 (1986), 123\u2013150.","journal-title":"Combinatorica"},{"key":"46_CR12","doi-asserted-by":"crossref","unstructured":"R. Karp, Reducibility among combinatorial problems, in: Complexity of computer computations (Miller, R.E., Thatcher, J.W., eds.), Plenum Press, 1972, 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"46_CR13","unstructured":"M. Karpinski and A.Z. Zelikovsky, New approximation algorithms for the Steiner tree problem, Electr. Colloq. Comput. Compl., TR95-030, 1995."},{"key":"46_CR14","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 Informatica15 (1981), 141\u2013145.","journal-title":"Acta Informatica"},{"key":"46_CR15","unstructured":"S. Lang, Algebra, Addison-Wesley Publishing Company, 1993."},{"key":"46_CR16","unstructured":"L. Lov\u00e1sz, The matroid matching problem, Algebraic Methods in Graph Theory, Colloquia Mathematica Societatis J\u00e1nos Bolyai, Szeged (Hungary), 1978."},{"key":"46_CR17","first-page":"565","volume":"79","author":"L. Lov\u00e1sz","year":"1979","unstructured":"L. Lov\u00e1sz, On determinants, matchings and random algorithms, Fund. Comput. Theory79 (1979), 565\u2013574.","journal-title":"Fund. Comput. Theory"},{"key":"46_CR18","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"K. Mulmuley, U. Vazirani, and V. Vazirani, Matching is as easy as matrix inversion, Combinatorica7 (1987), 105\u2013113.","journal-title":"Combinatorica"},{"key":"46_CR19","first-page":"504","volume":"206","author":"V. Pan","year":"1985","unstructured":"V. Pan, Fast and efficient algorithms for the exact inversion of integer matrices, Fifth Annual Foundations of Software Technology and Theoretical Computer Science Conference (1985), LNCS 206, 504\u2013521.","journal-title":"LNCS"},{"key":"46_CR20","volume-title":"The Steiner Tree Problem. A Tour through Graphs, Algorithms, and Complexity","author":"H.J. Pr\u00f6mel","year":"1997","unstructured":"H.J. Pr\u00f6mel and A. Steger, The Steiner Tree Problem. A Tour through Graphs, Algorithms, and Complexity, Vieweg Verlag, Wiesbaden, to appear 1997."},{"key":"46_CR21","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0020-0190(93)90019-6","volume":"45","author":"F. Suraweera","year":"1993","unstructured":"F. Suraweera and P. Bhattacharya, An O(log m) parallel algorithm for the minimum spanning tree problem, Inf. Proc. Lett.45 (1993), 159\u2013163.","journal-title":"Inf. Proc. Lett."},{"key":"46_CR22","first-page":"573","volume":"24","author":"H. Takahashi","year":"1980","unstructured":"H. Takahashi and A. Matsuyama, An approximate solution for the Steiner problem in graphs, Math. Japonica24 (1980), 573\u2013577.","journal-title":"Math. Japonica"},{"key":"46_CR23","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A.Z. Zelikovsky","year":"1993","unstructured":"A.Z. Zelikovsky, An 11\/6-approximation algorithm for the network Steiner problem, Algorithmica9 (1993), 463\u2013470.","journal-title":"Algorithmica"},{"key":"46_CR24","unstructured":"A.Z. Zelikovsky, Better approximation algorithms for the network and Euclidean Steiner tree problems, Technical Report, Kishinev, 1995."}],"container-title":["Lecture Notes in Computer Science","STACS 97"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0023489","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,4]],"date-time":"2019-02-04T18:23:14Z","timestamp":1549304594000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0023489"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540626169","9783540683421"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/bfb0023489","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997]]}}}