{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:00Z","timestamp":1759638300505},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,4,12]],"date-time":"2014-04-12T00:00:00Z","timestamp":1397260800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,8]]},"DOI":"10.1007\/s00453-014-9882-8","type":"journal-article","created":{"date-parts":[[2014,4,11]],"date-time":"2014-04-11T20:59:21Z","timestamp":1397249961000},"page":"914-939","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Restricted and Swap Common Superstring: A Multivariate Algorithmic Perspective"],"prefix":"10.1007","volume":"72","author":[{"given":"Paola","family":"Bonizzoni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Riccardo","family":"Dondi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giancarlo","family":"Mauri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Italo","family":"Zoppis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,4,12]]},"reference":[{"issue":"1\u20132","key":"9882_CR1","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1\u20132), 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9882_CR2","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"issue":"3","key":"9882_CR3","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0020-0190(98)00151-3","volume":"68","author":"A Amir","year":"1998","unstructured":"Amir, A., Landau, G.M., Lewenstein, M., Lewenstein, N.: Efficient special cases of pattern matching with swaps. Inform. Process. Lett. 68(3), 125\u2013132 (1998)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"9882_CR4","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1006\/jagm.2000.1120","volume":"37","author":"A Amir","year":"2000","unstructured":"Amir, A., Aumann, Y., Landau, G.M., Lewenstein, M., Lewenstein, N.: Pattern matching with swaps. J. Algorithm. 37(2), 247\u2013266 (2000)","journal-title":"J. Algorithm."},{"issue":"1","key":"9882_CR5","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s00453-005-1192-8","volume":"45","author":"A Amir","year":"2006","unstructured":"Amir, A., Eisenberg, E., Porat, E.: Swap and mismatch edit distance. Algorithmica 45(1), 109\u2013120 (2006)","journal-title":"Algorithmica"},{"key":"9882_CR6","first-page":"190","volume":"2005","author":"YJP Ardila","year":"2005","unstructured":"Ardila, Y.J.P., Iliopoulos, C.S., Landau, G.M., Mohamed, M.: Approximation algorithm for the cyclic swap problem. Stringology 2005, 190\u2013200 (2005)","journal-title":"Stringology"},{"key":"9882_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"G Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag, Heidelberg (1999)"},{"issue":"4","key":"9882_CR8","doi-asserted-by":"crossref","first-page":"630","DOI":"10.1145\/179812.179818","volume":"41","author":"A Blum","year":"1994","unstructured":"Blum, A., Jiang, T., Li, M., Tromp, J., Yannakakis, M.: Linear approximation of shortest superstrings. J. ACM 41(4), 630\u2013647 (1994)","journal-title":"J. ACM"},{"issue":"8","key":"9882_CR9","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9882_CR10","first-page":"165","volume":"2011","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: a new technique for kernelization lower bounds. Proc. STACS 2011, 165\u2013176 (2011)","journal-title":"Proc. STACS"},{"issue":"35","key":"9882_CR11","doi-asserted-by":"crossref","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9882_CR12","first-page":"49","volume":"2012","author":"P Bonizzoni","year":"2012","unstructured":"Bonizzoni, P., Dondi, R., Mauri, G., Zoppis, I.: Restricted and swap common superstring: a parameterized view. Proc. IPEC 2012, 49\u201360 (2012)","journal-title":"Proc. IPEC"},{"key":"9882_CR13","doi-asserted-by":"crossref","unstructured":"Clifford, R., Gotthilf, Z., Lewenstein, M., Popa, A.: Restricted common superstring and restricted common supersequence. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 467\u2013478. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-21458-5_39"},{"key":"9882_CR14","doi-asserted-by":"crossref","unstructured":"Fellows, M.R.: Towards fully multivariate algorithmics: some new results and directions in parameter ecology. In: Kratochv\u00edl, J., Miller, M. (eds.) IWOCA 2009. LNCS, vol. 5874, pp. 2\u201310. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-10217-2_2"},{"issue":"1","key":"9882_CR15","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"9882_CR16","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"9882_CR17","doi-asserted-by":"crossref","unstructured":"Gotthilf, Z., Lewenstein, M., Popa, A.: On shortest common superstring and swap permutations. In: Ch\u00e1vez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 270\u2013278. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-16321-0_28"},{"key":"9882_CR18","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences\u2014Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences\u2014Computer Science and Computational Biology. Cambridge University Press, New York (1997)"},{"key":"9882_CR19","doi-asserted-by":"crossref","unstructured":"Mucha, M.; Sankowski, P.: Maximum Matchings via Gaussian Elimination. In: Proceedings of 45st IEEE Symposium. Foundations of Computer Science, pp. 248\u2013255 (2004)","DOI":"10.1109\/FOCS.2004.40"},{"key":"9882_CR20","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"9882_CR21","first-page":"17","volume":"2010","author":"R Niedermeier","year":"2010","unstructured":"Niedermeier, R.: Reflections on multivariate algorithmics and problem parameterization. Proc. STACS 2010, 17\u201332 (2010)","journal-title":"Proc. STACS"},{"key":"9882_CR22","doi-asserted-by":"crossref","unstructured":"Ott, S.: Lower bounds for approximating shortest superstrings over an alphabet of size 2. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol. 1665, pp. 55\u201364. Springer, Heidelberg (1999)","DOI":"10.1007\/3-540-46784-X_7"},{"key":"9882_CR23","volume-title":"Data Compression: Methods and Theory","author":"J Storer","year":"1988","unstructured":"Storer, J.: Data Compression: Methods and Theory. Computer Science Press, New York (1988)"},{"issue":"3","key":"9882_CR24","doi-asserted-by":"crossref","first-page":"954","DOI":"10.1137\/S0097539796324661","volume":"29","author":"Z Sweedyk","year":"1999","unstructured":"Sweedyk, Z.: A 2 $$\\frac{1}{2}$$ 1 2 -approximation algorithm for shortest superstring. SIAM J. Comput. 29(3), 954\u2013986 (1999)","journal-title":"SIAM J. Comput."},{"key":"9882_CR25","doi-asserted-by":"crossref","unstructured":"Vassilevska, V.: Explicit inapproximability bounds for the shortest superstring problem. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 793\u2013800. Springer, Heidelberg (2005)","DOI":"10.1007\/11549345_68"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9882-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9882-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9882-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:13Z","timestamp":1559137513000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9882-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4,12]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["9882"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9882-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4,12]]}}}