{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T16:55:10Z","timestamp":1725555310440},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642130724"},{"type":"electronic","value":"9783642130731"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-13073-1_17","type":"book-chapter","created":{"date-parts":[[2010,5,10]],"date-time":"2010-05-10T04:09:58Z","timestamp":1273464598000},"page":"180-191","source":"Crossref","is-referenced-by-count":4,"title":["The Steiner Tree Reoptimization Problem with Sharpened Triangle Inequality"],"prefix":"10.1007","author":[{"given":"Hans-Joachim","family":"B\u00f6ckenhauer","sequence":"first","affiliation":[]},{"given":"Karin","family":"Freiermuth","sequence":"additional","affiliation":[]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[]},{"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[]},{"given":"Andreas","family":"Sprock","sequence":"additional","affiliation":[]},{"given":"Bj\u00f6rn","family":"Steffen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"17_CR1","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1002\/net.10091","volume":"42","author":"C. Archetti","year":"2003","unstructured":"Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the traveling salesman problem. Networks\u00a042(3), 154\u2013159 (2003)","journal-title":"Networks"},{"key":"17_CR2","unstructured":"Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the 0-1 knapsack problem. Tech. Rep. 267, University of Brescia (2006)"},{"key":"17_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/11785293_20","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"G. Ausiello","year":"2006","unstructured":"Ausiello, G., Escoffier, B., Monnot, J., Paschos, V.T.: Reoptimization of minimum and maximum traveling salesman\u2019s tours. In: Arge, L., Freivalds, R.V. (eds.) SWAT 2006. LNCS, vol.\u00a04059, pp. 196\u2013207. Springer, Heidelberg (2006)"},{"issue":"4","key":"17_CR4","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M.W. Bern","year":"1989","unstructured":"Bern, M.W., Plassmann, P.E.: The Steiner problem with edge lengths 1 and 2. Inf. Process. Lett.\u00a032(4), 171\u2013176 (1989)","journal-title":"Inf. Process. Lett."},{"key":"17_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-540-69903-3_24","volume-title":"Algorithm Theory \u2013 SWAT 2008","author":"D. Bil\u00f2","year":"2008","unstructured":"Bil\u00f2, D., B\u00f6ckenhauer, H.J., Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., M\u00f6mke, T., Widmayer, P., Zych, A.: Reoptimization of Steiner trees. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol.\u00a05124, pp. 258\u2013269. Springer, Heidelberg (2008)"},{"key":"17_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-642-02441-2_8","volume-title":"Combinatorial Pattern Matching","author":"D. Bil\u00f2","year":"2009","unstructured":"Bil\u00f2, D., B\u00f6ckenhauer, H.J., Komm, D., Kr\u00e1lovi\u010d, R., M\u00f6mke, T., Seibert, S., Zych, A.: Reoptimization of the shortest common superstring problem. In: Kucherov, G., Ukkonen, E. (eds.) CPM 2009. LNCS, vol.\u00a05577, pp. 78\u201391. Springer, Heidelberg (2009)"},{"key":"17_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-540-93980-1_16","volume-title":"Approximation and Online Algorithms","author":"D. Bil\u00f2","year":"2009","unstructured":"Bil\u00f2, D., Widmayer, P., Zych, A.: Reoptimization of weighted graph and covering problems. In: Bampis, E., Skutella, M. (eds.) WAOA 2008. LNCS, vol.\u00a05426, pp. 201\u2013213. Springer, Heidelberg (2009)"},{"key":"17_CR8","series-title":".","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-0-387-34735-6_21","volume-title":"Proc.\u00a0of the 4th IFIP International Conference on Theoretical Computer Science (TCS 2006). IFIP","author":"H.J. B\u00f6ckenhauer","year":"2006","unstructured":"B\u00f6ckenhauer, H.J., Forlizzi, L., Hromkovi\u010d, J., Kneis, J., Kupke, J., Proietti, G., Widmayer, P.: Reusing optimal TSP solutions for locally modified input instances (extended abstract). In: Navarro, G., Bertossi, L.E., Kohayakawa, Y. (eds.) Proc.\u00a0of the 4th IFIP International Conference on Theoretical Computer Science (TCS 2006). IFIP., vol.\u00a0209, pp. 251\u2013270. Springer, New York (2006)"},{"key":"17_CR9","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0020-0190(00)00089-2","volume":"75","author":"H.J. B\u00f6ckenhauer","year":"2000","unstructured":"B\u00f6ckenhauer, H.J., Hromkovi\u010d, J., Klasing, R., Seibert, S., Unger, W.: Approximation algorithms for TSP with sharpened triangle inequality. Inf. Process. Lett.\u00a075, 133\u2013138 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"36","key":"17_CR10","doi-asserted-by":"publisher","first-page":"3428","DOI":"10.1016\/j.tcs.2008.04.039","volume":"410","author":"H.J. B\u00f6ckenhauer","year":"2009","unstructured":"B\u00f6ckenhauer, H.J., Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., M\u00f6mke, T., Rossmanith, P.: Reoptimization of Steiner trees: Changing the terminal set. Theor. Comput. Sci.\u00a0410(36), 3428\u20133435 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-540-77566-9_5","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"H.J. B\u00f6ckenhauer","year":"2008","unstructured":"B\u00f6ckenhauer, H.J., Hromkovi\u010d, J., M\u00f6mke, T., Widmayer, P.: On the hardness of reoptimization. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol.\u00a04910, pp. 50\u201365. Springer, Heidelberg (2008)"},{"key":"17_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/978-3-540-85238-4_12","volume-title":"Mathematical Foundations of Computer Science 2008","author":"H.J. B\u00f6ckenhauer","year":"2008","unstructured":"B\u00f6ckenhauer, H.J., Komm, D.: Reoptimization of the metric deadline TSP. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol.\u00a05162, pp. 156\u2013167. Springer, Heidelberg (2008)"},{"issue":"2","key":"17_CR13","first-page":"86","volume":"4","author":"B. Escoffier","year":"2009","unstructured":"Escoffier, B., Milani\u010d, M., Paschos, V.T.: Simple and fast reoptimizations for the Steiner tree problem. Algorithmic Oper. Res.\u00a04(2), 86\u201394 (2009)","journal-title":"Algorithmic Oper. Res."},{"issue":"4","key":"17_CR14","first-page":"634","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J.\u00a0ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"J.\u00a0ACM"},{"issue":"4","key":"17_CR15","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1002\/(SICI)1097-0037(199807)31:4<283::AID-NET8>3.0.CO;2-9","volume":"31","author":"M.M. Halld\u00f3rsson","year":"1998","unstructured":"Halld\u00f3rsson, M.M., Ueno, S., Nakao, H., Kajitani, Y.: Approximating Steiner trees in graphs with restricted weights. Networks\u00a031(4), 283\u2013292 (1998)","journal-title":"Networks"},{"key":"17_CR16","volume-title":"Annals of Discrete Mathematics","author":"F.K. Hwang","year":"1992","unstructured":"Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problems. In: Annals of Discrete Mathematics, vol.\u00a053. North-Holland, Amsterdam (1992)"},{"key":"17_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of computer computations, pp. 85\u2013103. Plenum, New York (1972)"},{"key":"17_CR18","volume-title":"Advanced Lectures in Mathematics","author":"H.J. Pr\u00f6mel","year":"2002","unstructured":"Pr\u00f6mel, H.J., Steger, A.: The Steiner Tree Problem. In: Advanced Lectures in Mathematics, Friedr. Vieweg & Sohn, Braunschweig (2002)"},{"key":"17_CR19","first-page":"770","volume-title":"Proc.\u00a0of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a02000)","author":"G. Robins","year":"2000","unstructured":"Robins, G., Zelikovsky, A.Z.: Improved Steiner tree approximation in graphs. In: Proc.\u00a0of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a02000), pp. 770\u2013779. ACM\/SIAM, New York (2000)"},{"issue":"1-2","key":"17_CR20","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(96)00042-X","volume":"72","author":"M.W. Sch\u00e4ffter","year":"1997","unstructured":"Sch\u00e4ffter, M.W.: Scheduling with forbidden sets. Discrete Appl. Math.\u00a072(1-2), 155\u2013166 (1997)","journal-title":"Discrete Appl. Math."},{"key":"17_CR21","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2004","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13073-1_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T22:09:22Z","timestamp":1552514962000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13073-1_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642130724","9783642130731"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13073-1_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}