{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:16:48Z","timestamp":1725491808437},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540755197"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-75520-3_11","type":"book-chapter","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T03:46:33Z","timestamp":1189741593000},"page":"99-110","source":"Crossref","is-referenced-by-count":12,"title":["On the Cost of Interchange Rearrangement in Strings"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tzvika","family":"Hartman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oren","family":"Kapah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avivit","family":"Levy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"11_CR1","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.dam.2004.04.010","volume":"146","author":"A. Bergeron","year":"2005","unstructured":"Bergeron, A.: A very elementary presentation of the Hannenhalli-Pevzner theory. Discrete Applied Mathematics\u00a0146(2), 134\u2013145 (2005)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"11_CR2","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/S089548019731994X","volume":"12","author":"A. Caprara","year":"1999","unstructured":"Caprara, A.: Sorting permutations by reversals and Eulerian cycle decompositions. SIAM journal on discrete mathematics\u00a012(1), 91\u2013110 (1999)","journal-title":"SIAM journal on discrete mathematics"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/300515.300516","volume":"46","author":"S. Hannenhalli","year":"1999","unstructured":"Hannenhalli, S., Pevzner, P.: Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals. Journal of the ACM\u00a046, 1\u201327 (1999)","journal-title":"Journal of the ACM"},{"key":"11_CR4","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V. Bafna","year":"1998","unstructured":"Bafna, V., Pevzner, P.: Sorting by transpositions. SIAM J. on Disc. Math.\u00a011, 221\u2013240 (1998)","journal-title":"SIAM J. on Disc. Math."},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0166-218X(96)00061-3","volume":"71","author":"S. Hannenhalli","year":"1996","unstructured":"Hannenhalli, S.: Polynomial algorithm for computing translocation distance between genomes. Discrete Applied Mathematics\u00a071, 137\u2013151 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR6","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 by block-interchanges. Information Processing Letters\u00a060, 165\u2013169 (1996)","journal-title":"Information Processing Letters"},{"issue":"5","key":"11_CR7","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1089\/106652703322539097","volume":"10","author":"L.S. Heath","year":"2003","unstructured":"Heath, L.S., Vergara, P.C.: Sorting by short swaps. J. of Comp. Biology\u00a010(5), 775\u2013789 (2003)","journal-title":"J. of Comp. Biology"},{"unstructured":"Christie, D.A.: Genome Rearrangement Problems. PhD thesis, University of Glasgow (1999)","key":"11_CR8"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S0895480103433550","volume":"19","author":"A.J. Radcliff","year":"2005","unstructured":"Radcliff, A.J., Scott, A.D., Wilmer, E.L.: Reversals and transpositions over finite alphabets. SIAM journal on discrete mathematics\u00a019, 224\u2013244 (2005)","journal-title":"SIAM journal on discrete mathematics"},{"key":"11_CR10","first-page":"527","volume":"34","author":"A. Cayley","year":"1849","unstructured":"Cayley, A.: Note on the theory of permutations. Philosophical Magazine\u00a034, 527\u2013529 (1849)","journal-title":"Philosophical Magazine"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0304-3975(85)90047-7","volume":"36","author":"M.R. Jerrum","year":"1985","unstructured":"Jerrum, M.R.: The complexity of finding minimum-length generator sequences. Theoretical Computer Science\u00a036, 265\u2013289 (1985)","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Amir, A., Aumann, Y., Benson, G., Levy, A., Lipsky, O., Porat, E., Skiena, S., Vishne, U.: Pattern matching with address errors: Rearrangement distances. In: Proc. 17th SODA, pp. 1221\u20131229 (2006)","key":"11_CR12","DOI":"10.1145\/1109557.1109692"},{"unstructured":"Bender, M.A., Ge, D., He, S., Hu, H., Pinter, R.Y., Skiena, S., Swidan, F.: Improved bounds on sorting with length-weighted reversals. In: Proc. 15th SODA, pp. 912\u2013921 (2004)","key":"11_CR13"},{"issue":"4","key":"11_CR14","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/0210054","volume":"10","author":"I. Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of some edge-partition problems. SIAM Journal of Computing\u00a010(4), 713\u2013717 (1981)","journal-title":"SIAM Journal of Computing"},{"key":"11_CR15","volume-title":"Sorting and Searching","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: The Art of Computer Programming. In: Sorting and Searching, Reading, Mass, vol.\u00a03, Addison-Wesley, London, UK (1973)"},{"issue":"2","key":"11_CR16","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmoc efficiency for network flow problems. Journal of The ACM (JACM)\u00a019(2), 248\u2013264 (1972)","journal-title":"Journal of The ACM (JACM)"},{"issue":"3","key":"11_CR17","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. Journal of The ACM (JACM)\u00a034(3), 596\u2013615 (1987)","journal-title":"Journal of The ACM (JACM)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75520-3_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:22:43Z","timestamp":1619518963000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75520-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540755197"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75520-3_11","relation":{},"subject":[]}}