{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:56Z","timestamp":1759637936104},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662447529"},{"type":"electronic","value":"9783662447536"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44753-6_2","type":"book-chapter","created":{"date-parts":[[2014,8,15]],"date-time":"2014-08-15T12:08:34Z","timestamp":1408104514000},"page":"14-25","source":"Crossref","is-referenced-by-count":3,"title":["Improved Approximation for the Maximum Duo-Preservation String Mapping Problem"],"prefix":"10.1007","author":[{"given":"Nicolas","family":"Boria","sequence":"first","affiliation":[]},{"given":"Adam","family":"Kurpisz","sequence":"additional","affiliation":[]},{"given":"Samuli","family":"Lepp\u00e4nen","sequence":"additional","affiliation":[]},{"given":"Monaldo","family":"Mastrolilli","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"2_CR1","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s002240000113","volume":"32","author":"P. Berman","year":"1999","unstructured":"Berman, P., Fujito, T.: On Approximation Properties of the Independent Set Problem for Low Degree Graphs. Theory of Computing Systems\u00a032(2), 115\u2013132 (1999)","journal-title":"Theory of Computing Systems"},{"unstructured":"Berman, P., F\u00fcrer, M.: Approximating Maximum Independent Set in Bounded Degree Graphs. In: Sleator, D.D. (ed.) SODA, pp. 365\u2013371. ACM\/SIAM (1994)","key":"2_CR2"},{"key":"2_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-48523-6_17","volume-title":"Automata, Languages and Programming","author":"P. Berman","year":"1999","unstructured":"Berman, P., Karpinski, M.: On Some Tighter Inapproximability Results (Extended Abstract). In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol.\u00a01644, pp. 200\u2013209. Springer, Heidelberg (1999)"},{"key":"2_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-642-40453-5_19","volume-title":"Algorithms in Bioinformatics","author":"L. Bulteau","year":"2013","unstructured":"Bulteau, L., Fertin, G., Komusiewicz, C., Rusu, I.: A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications. In: Darling, A., Stoye, J. (eds.) WABI 2013. LNCS, vol.\u00a08126, pp. 244\u2013258. Springer, Heidelberg (2013)"},{"key":"2_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/3-540-46784-X_30","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. Chen","year":"1999","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex Cover: Further Observations and Further Improvements. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol.\u00a01665, pp. 313\u2013324. Springer, Heidelberg (1999)"},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2014.02.017","volume":"530","author":"W. Chen","year":"2014","unstructured":"Chen, W., Chen, Z., Samatova, N.F., Peng, L., Wang, J., Tang, M.: Solving the maximum duo-preservation string mapping problem with linear programming. Theoretical Computer Science\u00a0530, 1\u201311 (2014)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"2_CR7","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1109\/TCBB.2005.48","volume":"2","author":"X. Chen","year":"2005","unstructured":"Chen, X., Zheng, J., Fu, Z., Nan, P., Zhong, Y., Lonardi, S., Jiang, T.: Assignment of Orthologous Genes via Genome Rearrangement. Transactions on Computational Biology and Bioinformatics\u00a02(4), 302\u2013315 (2005)","journal-title":"Transactions on Computational Biology and Bioinformatics"},{"key":"2_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-540-27821-4_8","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Chrobak","year":"2004","unstructured":"Chrobak, M., Kolman, P., Sgall, J.: The Greedy Algorithm for the Minimum Common String Partition Problem. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol.\u00a03122, pp. 84\u201395. Springer, Heidelberg (2004)"},{"issue":"1","key":"2_CR9","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1186810.1186812","volume":"3","author":"Graham Cormode","year":"2007","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. ACM Transactions on Algorithms\u00a03(1) (2007)","journal-title":"ACM Transactions on Algorithms"},{"key":"2_CR10","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/978-3-540-87361-7_8","volume-title":"Algorithms in Bioinformatics","author":"P. Damaschke","year":"2008","unstructured":"Damaschke, P.: Minimum Common String Partition Parameterized. In: Crandall, K.A., Lagergren, J. (eds.) WABI 2008. LNCS (LNBI), vol.\u00a05251, pp. 87\u201398. Springer, Heidelberg (2008)"},{"doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity, p. 530. Springer (1999)","key":"2_CR11","DOI":"10.1007\/978-1-4612-0515-9"},{"unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., San Francisco (1979)","key":"2_CR12"},{"key":"2_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1007\/978-3-540-30551-4_43","volume-title":"Algorithms and Computation","author":"A. Goldstein","year":"2004","unstructured":"Goldstein, A., Kolman, P., Zheng, J.: Minimum Common String Partition Problem: Hardness and Approximations. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 484\u2013495. Springer, Heidelberg (2004)"},{"issue":"4","key":"2_CR14","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s10878-010-9370-2","volume":"23","author":"H. Jiang","year":"2012","unstructured":"Jiang, H., Zhu, B., Zhu, D., Zhu, H.: Minimum common string partition revisited. Journal of Combinatorial Optimization\u00a023(4), 519\u2013527 (2012)","journal-title":"Journal of Combinatorial Optimization"},{"issue":"3","key":"2_CR15","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/j.dam.2006.05.011","volume":"155","author":"P. Kolman","year":"2007","unstructured":"Kolman, P., Walen, T.: Approximating reversal distance for strings with bounded number of duplicates. Discrete Applied Mathematics\u00a0155(3), 327\u2013336 (2007)","journal-title":"Discrete Applied Mathematics"},{"doi-asserted-by":"crossref","unstructured":"Kolman, P., Walen, T.: Reversal Distance for Strings with Duplicates: Linear Time Approximation using Hitting Set. Electronic Journal of Combinatorics\u00a014(1) (2007)","key":"2_CR16","DOI":"10.1007\/11970125_22"},{"key":"2_CR17","first-page":"102","volume-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Laurent Bulteau","year":"2013","unstructured":"Bulteau, L., Komusiewicz, C.: Minimum common string partition parameterized by partition size is fixed-parameter tractable. In: SODA, pp. 102\u2013121 (2014)"},{"key":"2_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/3-540-56939-1_60","volume-title":"Automata, Languages and Programming","author":"C. Lund","year":"1993","unstructured":"Lund, C., Yannakakis, M.: The Approximation of Maximum Subgraph Problems. In: Lingas, A., Karlsson, R.G., Carlsson, S. (eds.) ICALP 1993. LNCS, vol.\u00a0700, pp. 40\u201351. Springer, Heidelberg (1993)"},{"key":"2_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1227161.1402297","volume":"12","author":"Krister M. Swenson","year":"2008","unstructured":"Swenson, K.M., Marron, M., Earnest-DeYoung, J.V., Moret, B.M.E.: Approximating the true evolutionary distance between two genomes. ACM Journal of Experimental Algorithmics\u00a012 (2008)","journal-title":"Journal of Experimental Algorithmics"}],"container-title":["Lecture Notes in Computer Science","Algorithms in Bioinformatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44753-6_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T00:55:59Z","timestamp":1565744159000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44753-6_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662447529","9783662447536"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44753-6_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}