{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:00Z","timestamp":1759638960795},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_55","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T07:44:05Z","timestamp":1308555845000},"page":"654-665","source":"Crossref","is-referenced-by-count":9,"title":["Sorting by Transpositions Is Difficult"],"prefix":"10.1007","author":[{"given":"Laurent","family":"Bulteau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Fertin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Irena","family":"Rusu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"55_CR1","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/j.jcss.2009.03.001","volume":"75","author":"A. Amir","year":"2009","unstructured":"Amir, A., Aumann, Y., Benson, G., Levy, A., Lipsky, O., Porat, E., Skiena, S., Vishne, U.: Pattern matching with address errors: Rearrangement distances. J. Comput. Syst. Sci.\u00a075(6), 359\u2013370 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"55_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-540-75530-2_4","volume-title":"String Processing and Information Retrieval","author":"A. Amir","year":"2007","unstructured":"Amir, A., Aumann, Y., Indyk, P., Levy, A., Porat, E.: Efficient computations of \u21131 and \u2113?8? rearrangement distances. In: Ziviani, N., Baeza-Yates, R.A. (eds.) SPIRE 2007. LNCS, vol.\u00a04726, pp. 39\u201349. Springer, Heidelberg (2007)"},{"key":"55_CR3","unstructured":"Bafna, V., Pevzner, P.A.: Sorting permutations by transpositions. In: SODA, pp. 614\u2013623 (1995)"},{"issue":"2","key":"55_CR4","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V. Bafna","year":"1998","unstructured":"Bafna, V., Pevzner, P.A.: Sorting by transpositions. SIAM J. Discrete Math.\u00a011(2), 224\u2013240 (1998)","journal-title":"SIAM J. Discrete Math."},{"key":"55_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-540-73437-6_15","volume-title":"Combinatorial Pattern Matching","author":"M. Beno\u00eet-Gagn\u00e9","year":"2007","unstructured":"Beno\u00eet-Gagn\u00e9, M., Hamel, S.: A new and faster method of sorting by transpositions. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 131\u2013141. Springer, Heidelberg (2007)"},{"key":"55_CR6","unstructured":"Bongartz, D.: Algorithmic Aspects of Some Combinatorial Problems in Bioinformatics. PhD thesis, RWTH Aachen University, Germany (2006)"},{"key":"55_CR7","doi-asserted-by":"crossref","unstructured":"Bulteau, L., Fertin, G., Rusu, I.: Sorting by Transpositions is Difficult. CoRR abs\/1011.1157 (2010)","DOI":"10.1007\/978-3-642-22006-7_55"},{"key":"55_CR8","first-page":"468","volume-title":"HICSS","author":"B. Chitturi","year":"2008","unstructured":"Chitturi, B., Sudborough, I.H.: Bounding prefix transposition distance for strings and permutations. In: HICSS, p. 468. IEEE Computer Society, Los Alamitos (2008)"},{"issue":"4","key":"55_CR9","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(96)00155-X","volume":"60","author":"D.A. Christie","year":"1996","unstructured":"Christie, D.A.: Sorting permutations by block-interchanges. Inf. Process. Lett.\u00a060(4), 165\u2013169 (1996)","journal-title":"Inf. Process. Lett."},{"key":"55_CR10","unstructured":"Christie, D.A.: Genome Rearrangement Problems. PhD thesis, University of Glasgow, Scotland (1998)"},{"issue":"2","key":"55_CR11","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/S0895480197331995","volume":"14","author":"D.A. Christie","year":"2001","unstructured":"Christie, D.A., Irving, R.W.: Sorting strings by reversals and by transpositions. SIAM J. Discrete Math.\u00a014(2), 193\u2013206 (2001)","journal-title":"SIAM J. Discrete Math."},{"key":"55_CR12","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. In: SODA, pp. 667\u2013676 (2002)"},{"key":"55_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/3-540-45735-6_7","volume-title":"String Processing and Information Retrieval","author":"Z. Dias","year":"2002","unstructured":"Dias, Z., Meidanis, J.: Sorting by prefix transpositions. In: Laender, A.H.F., Oliveira, A.L. (eds.) SPIRE 2002. LNCS, vol.\u00a02476, pp. 65\u201376. Springer, Heidelberg (2002)"},{"issue":"4","key":"55_CR14","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1109\/TCBB.2006.44","volume":"3","author":"I. Elias","year":"2006","unstructured":"Elias, I., Hartman, T.: A 1.375-approximation algorithm for sorting by transpositions. IEEE\/ACM Trans. Comput. Biology Bioinform.\u00a03(4), 369\u2013379 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biology Bioinform."},{"issue":"1-3","key":"55_CR15","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/S0012-365X(01)00150-9","volume":"241","author":"H. Eriksson","year":"2001","unstructured":"Eriksson, H., Eriksson, K., Karlander, J., Svensson, L.J., W\u00e4stlund, J.: Sorting a bridge hand. Discrete Mathematics\u00a0241(1-3), 289\u2013300 (2001)","journal-title":"Discrete Mathematics"},{"key":"55_CR16","doi-asserted-by":"crossref","unstructured":"Feng, J., Zhu, D.: Faster algorithms for sorting by transpositions and sorting by block interchanges. ACM Transactions on Algorithms 3(3) (2007)","DOI":"10.1145\/1273340.1273341"},{"key":"55_CR17","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9780262062824.001.0001","volume-title":"Combinatorics of genome rearrangements","author":"G. Fertin","year":"2009","unstructured":"Fertin, G., Labarre, A., Rusu, I., Tannier, \u00c9., Vialette, S.: Combinatorics of genome rearrangements. The MIT Press, Cambridge (2009)"},{"key":"55_CR18","unstructured":"Gu, Q.-P., Peng, S., Chen, Q.M.: Sorting permutations and its applications in genome analysis. Lectures on Mathematics in the Life Science, vol.\u00a026, pp. 191\u2013201 (1999)"},{"key":"55_CR19","unstructured":"Guyer, S.A., Heath, L.S., Vergara, J.P.: Subsequence and run heuristics for sorting by transpositions. Technical report, Virginia State University (1997)"},{"issue":"2","key":"55_CR20","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/j.ic.2005.09.002","volume":"204","author":"T. Hartman","year":"2006","unstructured":"Hartman, T., Shamir, R.: A simpler and faster 1.5-approximation algorithm for sorting by transpositions. Inf. Comput.\u00a0204(2), 275\u2013290 (2006)","journal-title":"Inf. Comput."},{"key":"55_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/11970125_22","volume-title":"Approximation and Online Algorithms","author":"P. Kolman","year":"2007","unstructured":"Kolman, P., Wale\u0144, T.: Reversal distance for strings with duplicates: Linear time approximation using hitting set. In: Erlebach, T., Kaklamanis, C. (eds.) WAOA 2006. LNCS, vol.\u00a04368, pp. 279\u2013289. Springer, Heidelberg (2007)"},{"issue":"4","key":"55_CR22","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1109\/TCBB.2006.56","volume":"3","author":"A. Labarre","year":"2006","unstructured":"Labarre, A.: New bounds and tractable instances for the transposition distance. IEEE\/ACM Trans. Comput. Biology Bioinform.\u00a03(4), 380\u2013394 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biology Bioinform."},{"key":"55_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/978-3-540-87744-8_53","volume-title":"Algorithms - ESA 2008","author":"A. Labarre","year":"2008","unstructured":"Labarre, A.: Edit distances and factorisations of even permutations. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol.\u00a05193, pp. 635\u2013646. Springer, Heidelberg (2008)"},{"key":"55_CR24","unstructured":"Qi, X.-Q.: Combinatorial Algorithms of Genome Rearrangements in Bioinformatics. PhD thesis, University of Shandong, China (2006)"},{"key":"55_CR25","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S0895480103433550","volume":"19","author":"A.J. Radcliffe","year":"2005","unstructured":"Radcliffe, A.J., Scott, A.D., Wilmer, A.L.: Reversals and transpositions over finite alphabets. SIAM J. Discret. Math.\u00a019, 224\u2013244 (2005)","journal-title":"SIAM J. Discret. Math."},{"key":"55_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/3-540-45452-7_9","volume-title":"Combinatorial Pattern Matching","author":"D. Shapira","year":"2002","unstructured":"Shapira, D., Storer, J.A.: Edit distance with move operations. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol.\u00a02373, pp. 85\u201398. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_55","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,25]],"date-time":"2021-11-25T23:24:43Z","timestamp":1637882683000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}