{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:46:24Z","timestamp":1759063584517},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2010,6,15]],"date-time":"2010-06-15T00:00:00Z","timestamp":1276560000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,10]]},"DOI":"10.1007\/s00453-010-9419-8","type":"journal-article","created":{"date-parts":[[2010,6,14]],"date-time":"2010-06-14T14:08:34Z","timestamp":1276524514000},"page":"227-251","source":"Crossref","is-referenced-by-count":12,"title":["Reoptimization of the Shortest Common Superstring Problem"],"prefix":"10.1007","volume":"61","author":[{"given":"Davide","family":"Bil\u00f2","sequence":"first","affiliation":[]},{"given":"Hans-Joachim","family":"B\u00f6ckenhauer","sequence":"additional","affiliation":[]},{"given":"Dennis","family":"Komm","sequence":"additional","affiliation":[]},{"given":"Richard","family":"Kr\u00e1lovi\u010d","sequence":"additional","affiliation":[]},{"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[]},{"given":"Sebastian","family":"Seibert","sequence":"additional","affiliation":[]},{"given":"Anna","family":"Zych","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,6,15]]},"reference":[{"issue":"3","key":"9419_CR1","doi-asserted-by":"crossref","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 42(3), 154\u2013159 (2003)","journal-title":"Networks"},{"key":"9419_CR2","unstructured":"Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the 0-1 knapsack problem. Technical Report 267, University of Brescia (2006)"},{"key":"9419_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/11785293_20","volume-title":"Proc. of the 10th Scandinavian Workshop on Algorithm Theory (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.) Proc. of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006). Lecture Notes in Computer Science, vol. 4059, pp. 196\u2013207. Springer, Berlin (2006)"},{"key":"9419_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1007\/978-3-540-69903-3_24","volume-title":"Proc. of the 11th Scandinavian Workshop on Algorithm Theory (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.) Proc. of the 11th Scandinavian Workshop on Algorithm Theory (SWAT 2008). Lecture Notes in Computer Science, vol. 5124, pp. 258\u2013269. Springer, Berlin (2008)"},{"key":"9419_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/978-3-540-93980-1_16","volume-title":"Proc. of the 6th International Workshop on Approximation and Online Algorithms (WAOA 2008)","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.) Proc. of the 6th International Workshop on Approximation and Online Algorithms (WAOA 2008). Lecture Notes in Computer Science, vol. 5426, pp. 201\u2013213. Springer, Berlin (2009)"},{"key":"9419_CR6","series-title":"Natural Computing Series","volume-title":"Algorithmic Aspects of Bioinformatics","author":"H.-J. B\u00f6ckenhauer","year":"2007","unstructured":"B\u00f6ckenhauer, H.-J., Bongartz, D.: Algorithmic Aspects of Bioinformatics. Natural Computing Series, Springer, Berlin (2007)"},{"key":"9419_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1007\/978-3-540-85238-4_12","volume-title":"Proc. of the 33th International Symposium on Mathematical Foundations of Computer Science (MFCS 2008)","author":"H.-J. B\u00f6ckenhauer","year":"2008","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D.: Reoptimization of the metric deadline TSP. In: Ochmanski, E., Tyszkiewicz, J. (eds.) Proc. of the 33th International Symposium on Mathematical Foundations of Computer Science (MFCS 2008). Lecture Notes in Computer Science, vol. 5162, pp. 156\u2013167. Springer, Berlin (2008)"},{"key":"9419_CR8","series-title":"IFIP","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/978-0-387-34735-6_21","volume-title":"Proc. of the 4th IFIP International Conference on Theoretical Computer Science (TCS 2006)","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,\u00a0G., Bertossi, L.E., Kohayakawa, Y. (eds.) Proc. of the 4th IFIP International Conference on Theoretical Computer Science (TCS 2006). IFIP, vol. 209, pp. 251\u2013270. Springer, New York (2006)"},{"key":"9419_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/978-3-540-77566-9_5","volume-title":"Proc. of the 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2008)","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.) Proc. of the 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2008). Lecture Notes in Computer Science, vol. 4910, pp. 50\u201365. Springer, Berlin (2008)"},{"issue":"36","key":"9419_CR10","doi-asserted-by":"crossref","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. 410(36), 3428\u20133435 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9419_CR11","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. 4(2), 86\u201394 (2009)","journal-title":"Algorithmic Oper. Res."},{"issue":"1","key":"9419_CR12","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0022-0000(80)90004-5","volume":"20","author":"J. Gallant","year":"1980","unstructured":"Gallant, J., Maier, D., Storer, J.A.: On finding minimal length superstrings. J. Comput. Syst. Sci. 20(1), 50\u201358 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9419_CR13","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.ipl.2004.09.012","volume":"93","author":"H. Kaplan","year":"2005","unstructured":"Kaplan, H., Shafrir, N.: The greedy algorithm for shortest superstrings. Inf. Process. Lett. 93(1), 13\u201317 (2005)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9419_CR14","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1145\/1082036.1082041","volume":"52","author":"H. Kaplan","year":"2005","unstructured":"Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM 52(4), 602\u2013626 (2005)","journal-title":"J. ACM"},{"issue":"1\u20132","key":"9419_CR15","doi-asserted-by":"crossref","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. 72(1\u20132), 155\u2013166 (1997)","journal-title":"Discrete Appl. Math."},{"key":"9419_CR16","series-title":"Natural Computing Series","volume-title":"Introduction to Computational Molecular Biology","author":"C. Setubal","year":"1997","unstructured":"Setubal, C., Meidanis, J.: Introduction to Computational Molecular Biology. Natural Computing Series, PWS Publishing Company, Boston (1997)"},{"issue":"3","key":"9419_CR17","doi-asserted-by":"crossref","first-page":"954","DOI":"10.1137\/S0097539796324661","volume":"29","author":"Z. Sweedyk","year":"2000","unstructured":"Sweedyk, Z.: A $2\\frac{1}{2}$ -approximation algorithm for shortest superstring. SIAM J. Comput. 29(3), 954\u2013986 (2000)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9419_CR18","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0304-3975(88)90167-3","volume":"57","author":"J. Tarhio","year":"1988","unstructured":"Tarhio, J., Ukkonen, E.: A greedy approximation algorithm for constructing shortest common superstrings. Theor. Comput. Sci. 57(1), 131\u2013145 (1988)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"9419_CR19","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0166-218X(98)00151-6","volume":"91","author":"S. Hoesel van","year":"1999","unstructured":"van Hoesel, S., Wagelmans, A.: On the complexity of postoptimality analysis of 0\/1 programs. Discrete Appl. Math. 91(1\u20133), 251\u2013263 (1999)","journal-title":"Discrete Appl. Math."},{"key":"9419_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1007\/11549345_68","volume-title":"Proc. of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005)","author":"V. Vassilevska","year":"2005","unstructured":"Vassilevska, V.: Explicit inapproximability bounds for the shortest superstring problem. In: Jedrzejowicz, J., Szepietowski, A. (eds.) Proc. of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005). Lecture Notes in Computer Science, vol. 3618, pp. 793\u2013800. Springer, Berlin (2005)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9419-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9419-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9419-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:06Z","timestamp":1559137506000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9419-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,15]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["9419"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9419-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6,15]]}}}