{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T02:51:46Z","timestamp":1742957506967,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319148953"},{"type":"electronic","value":"9783319148960"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-14896-0_6","type":"book-chapter","created":{"date-parts":[[2014,12,31]],"date-time":"2014-12-31T06:06:08Z","timestamp":1420005968000},"page":"60-72","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Steiner Tree 1.39-Approximation in Practice"],"prefix":"10.1007","author":[{"given":"Stephan","family":"Beyer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Chimani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,1,1]]},"reference":[{"issue":"3","key":"6_CR1","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1006\/jagm.1994.1041","volume":"17","author":"P Berman","year":"1994","unstructured":"Berman, P., Ramaiyer, V.: Improved Approximations for the Steiner Tree Problem. J. Algorithms 17(3), 381\u2013408 (1994)","journal-title":"J. Algorithms"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Borchers, A., Du, D.Z.: The $$k$$-Steiner ratio in graphs. In: STOC 1995, pp. 641\u2013649. ACM (1995)","DOI":"10.1145\/225058.225282"},{"issue":"1","key":"6_CR3","doi-asserted-by":"publisher","first-page":"6:1","DOI":"10.1145\/2432622.2432628","volume":"60","author":"J Byrka","year":"2013","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: Steiner Tree Approximation via Iterative Randomized Rounding. Journal of the ACM 60(1), 6:1\u20136:33 (2013)","journal-title":"Journal of the ACM"},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-642-25591-5_6","volume-title":"Algorithms and Computation","author":"M Chimani","year":"2011","unstructured":"Chimani, M., Woste, M.: Contraction-based steiner tree approximations in practice. In: Asano, T., Nakano, S., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 40\u201349. Springer, Heidelberg (2011)"},{"issue":"3","key":"6_CR5","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2008.06.046","volume":"406","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: The Steiner tree problem on graphs: Inapproximability results. Theor. Comput. Sci. 406(3), 207\u2013214 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Olver, N., Rothvo\u00df, T., Zenklusen, R.: Matroids and integrality gaps for hypergraphic steiner tree relaxations. In: STOC 2012, pp. 1161\u20131176. ACM (2012)","DOI":"10.1145\/2213977.2214081"},{"issue":"2","key":"6_CR7","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A General Approximation Technique for Constrained Forest Problems. SIAM J. Comput. 24(2), 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"key":"6_CR8","unstructured":"Hougardy, S., Pr\u00f6mel, H.J.: A 1.598 approximation algorithm for the steiner problem in graphs. In: SODA 1999, pp. 448\u2013453. ACM\/SIAM (1999)"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"6_CR10","unstructured":"Karpinski, M., Zelikovsky, A.: 1.757 and 1.267-Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems. ECCC 2, TR95-003 (1995)"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Koch, T., Martin, A., Vo\u00df, S.: SteinLib: An Updated Library on Steiner Tree Problems in Graphs. ZIB-Report 00\u201337 (2000). http:\/\/steinlib.zib.de","DOI":"10.1007\/978-1-4613-0255-1_9"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF00288961","volume":"15","author":"LT Kou","year":"1981","unstructured":"Kou, L.T., Markowsky, G., Berman, L.: A Fast Algorithm for Steiner Trees. Acta Informatica 15, 141\u2013145 (1981)","journal-title":"Acta Informatica"},{"issue":"3","key":"6_CR13","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0020-0190(88)90066-X","volume":"27","author":"K Mehlhorn","year":"1988","unstructured":"Mehlhorn, K.: A Faster Approximation Algorithm for the Steiner Problem in Graphs. Information Processing Letters 27(3), 125\u2013128 (1988)","journal-title":"Information Processing Letters"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. In: STOC 1988, pp. 229\u2013234. ACM (1988)","DOI":"10.1145\/62212.62233"},{"issue":"1\u20133","key":"6_CR15","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/S0166-218X(00)00319-X","volume":"112","author":"T Polzin","year":"2001","unstructured":"Polzin, T., Vahdati Daneshmand, S.: Improved Algorithms for the Steiner Problem in Networks. Discrete Applied Mathematics 112(1\u20133), 263\u2013300 (2001)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"6_CR16","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/S0167-6377(02)00185-2","volume":"31","author":"T Polzin","year":"2003","unstructured":"Polzin, T., Vahdati Daneshmand, S.: On Steiner trees and minimum spanning trees in hypergraphs. Operations Research Letters 31(1), 12\u201320 (2003)","journal-title":"Operations Research Letters"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/BFb0023489","volume-title":"STACS 97","author":"HJ Pr\u00f6mel","year":"1997","unstructured":"Pr\u00f6mel, H.J., Steger, A.: RNC-approximation algorithms for the steiner problem. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 559\u2013570. Springer, Heidelberg (1997)"},{"issue":"1","key":"6_CR18","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G Robins","year":"2005","unstructured":"Robins, G., Zelikovsky, A.: Tighter Bounds for Graph Steiner Tree Approximation. SIAM J. Discrete Math. 19(1), 122\u2013134 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"6_CR19","first-page":"573","volume":"24","author":"H Takahashi","year":"1980","unstructured":"Takahashi, H., Matsuyama, A.: An Approximate Solution for the Steiner Problem in Graphs. Mathematica Japonica 24, 573\u2013577 (1980)","journal-title":"Mathematica Japonica"},{"key":"6_CR20","unstructured":"Warme, D.M.: Spanning Trees in Hypergraphs with Application to Steiner Trees. Ph.D. thesis, University of Virginia (1998)"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Zelikovsky, A.: An 11\/6-Approximation Algorithm for the Steiner Problem on Graphs. Annals of Discrete Mathematics 51, 351\u2013354 (1992)","DOI":"10.1016\/S0167-5060(08)70655-1"},{"issue":"2","key":"6_CR22","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0020-0190(93)90201-J","volume":"46","author":"A Zelikovsky","year":"1993","unstructured":"Zelikovsky, A.: A Faster Approximation Algorithm for the Steiner Tree Problem in Graphs. Information Processing Letters 46(2), 79\u201383 (1993)","journal-title":"Information Processing Letters"},{"issue":"5","key":"6_CR23","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A Zelikovsky","year":"1993","unstructured":"Zelikovsky, A.: An 11\/6-Approximation Algorithm for the Network Steiner Problem. Algorithmica 9(5), 463\u2013470 (1993)","journal-title":"Algorithmica"},{"key":"6_CR24","unstructured":"Zelikovsky, A.: Better Approximation Bounds for the Network and Euclidean Steiner Tree Problems. Tech. rep. CS-96-06, University of Virginia (1995)"}],"container-title":["Lecture Notes in Computer Science","Mathematical and Engineering Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-14896-0_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,20]],"date-time":"2023-02-20T20:00:31Z","timestamp":1676923231000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-14896-0_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319148953","9783319148960"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-14896-0_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"1 January 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}