{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:35:53Z","timestamp":1742913353208,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319266251"},{"type":"electronic","value":"9783319266268"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-26626-8_44","type":"book-chapter","created":{"date-parts":[[2015,12,9]],"date-time":"2015-12-09T04:08:43Z","timestamp":1449634123000},"page":"601-616","source":"Crossref","is-referenced-by-count":2,"title":["The Influence of Preprocessing on Steiner Tree Approximations"],"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,12,9]]},"reference":[{"key":"44_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/978-3-319-14896-0_6","volume-title":"Mathematical and Engineering Methods in Computer Science","author":"S Beyer","year":"2014","unstructured":"Beyer, S., Chimani, M.: Steiner tree 1.39-approximation in practice. In: Hlin\u011bn\u00fd, P., Dvo\u0159\u00e1k, Z., Jaro\u0161, J., Kofro\u0148, J., Ko\u0159enek, J., Matula, P., Pala, K. (eds.) MEMICS 2014. LNCS, vol. 8934, pp. 60\u201372. Springer, Heidelberg (2014)"},{"key":"44_CR2","unstructured":"Beyer, S., Chimani, M.: Strong Steiner Tree Approximations inPractice. Submitted to Journal (2014). \n                      http:\/\/arxiv.org\/abs\/1409.8318"},{"issue":"1","key":"44_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. J. ACM 60(1), 6:1\u20136:33 (2013)","journal-title":"J. ACM"},{"key":"44_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)"},{"key":"44_CR5","unstructured":"Ciebiera, K., Godlewski, P., Sankowski, P., Wygocki, P.: Approximation Algorithms for Steiner Tree Problems Based on Universal Solution Frameworks. arXiv abs\/1410.7534 (2014). \n                      http:\/\/arxiv.org\/abs\/1410.7534"},{"key":"44_CR6","unstructured":"11th DIMACS Challenge. \n                      http:\/\/dimacs11.cs.princeton.edu\n                      \n                    . Bounds 12 September 2014"},{"issue":"3","key":"44_CR7","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"SE Dreyfus","year":"1971","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1(3), 195\u2013207 (1971)","journal-title":"Networks"},{"key":"44_CR8","unstructured":"Fischetti, M., Leitner, M., Ljubic, I., Luipersbeck, M., Monaci, M., Resch, M., Salvagnin, D., Sinnl, M.: Thinning out Steiner trees: a node-based model for uniform edge costs. In: 11th DIMACS Challenge (2014)"},{"key":"44_CR9","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"},{"key":"44_CR10","first-page":"1325","volume":"30","author":"M Junger","year":"2000","unstructured":"Junger, M., Thienel, S.: The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization. Softw.: Pract. Exp. 30, 1325\u20131352 (2000)","journal-title":"Softw.: Pract. Exp."},{"key":"44_CR11","unstructured":"Koch, T., Martin, A., Vo\u00df, S.: SteinLib: An Updated Library on Steiner Tree Problems in Graphs. ZIB-Report 00\u201337 (2000). \n                      http:\/\/steinlib.zib.de"},{"key":"44_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":"2\u20133","key":"44_CR13","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s10107-005-0660-x","volume":"105","author":"I Ljubic","year":"2006","unstructured":"Ljubic, I., Weiskircher, R., Pferschy, U., Klau, G.W., Mutzel, P., Fischetti, M.: An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem. Math. Program. 105(2\u20133), 427\u2013449 (2006)","journal-title":"Math. Program."},{"issue":"3","key":"44_CR14","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. Inf. Process. Lett. 27(3), 125\u2013128 (1988)","journal-title":"Inf. Process. Lett."},{"key":"44_CR15","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. In: STOC 1988, 229\u2013234. ACM (1988)","DOI":"10.1145\/62212.62233"},{"key":"44_CR16","unstructured":"Poggi de Arag\u00e3o, M., Ribeiro, C.C., Uchoa, E., Werneck, R.F.: Hybrid local search for the steiner problem in graphs. In: MIC 2001 (2001)"},{"key":"44_CR17","unstructured":"Pajor, T., Uchoa, E., Werneck, R.F.: A robust and scalable algorithm for the Steiner problem in graphs. In: 11th DIMACS Challenge (2014)"},{"issue":"1\u20133","key":"44_CR18","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 Appl. Math. 112(1\u20133), 263\u2013300 (2001)","journal-title":"Discrete Appl. Math."},{"key":"44_CR19","unstructured":"Polzin, T., Vahdati Daneshmand, S.: The Steiner tree challenge: an updated study. In: 11th DIMACS Challenge (2014)"},{"issue":"1","key":"44_CR20","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":"44_CR21","first-page":"573","volume":"24","author":"H Takahashi","year":"1980","unstructured":"Takahashi, H., Matsuyama, A.: An approximate solution for the Steiner problem in graphs. Math. Jpn. 24, 573\u2013577 (1980)","journal-title":"Math. Jpn."},{"key":"44_CR22","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/S0167-5060(08)70655-1","volume":"51","author":"A Zelikovsky","year":"1992","unstructured":"Zelikovsky, A.: An 11\/6-approximation algorithm for the Steiner problem on graphs. Ann. Discrete Math. 51, 351\u2013354 (1992)","journal-title":"Ann. Discrete Math."},{"issue":"2","key":"44_CR23","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. Inf. Process. Lett. 46(2), 79\u201383 (1993)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"44_CR24","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":"44_CR25","unstructured":"Zelikovsky, A.: Better Approximation Bounds for the Network and Euclidean Steiner Tree Problems. Technical report. CS-96-06, University of Virginia (1995)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-26626-8_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T17:11:13Z","timestamp":1559322673000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-26626-8_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319266251","9783319266268"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-26626-8_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}