{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T18:44:34Z","timestamp":1794336274518,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540291183","type":"print"},{"value":"9783540319511","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11561071_38","type":"book-chapter","created":{"date-parts":[[2005,10,6]],"date-time":"2005-10-06T08:46:24Z","timestamp":1128588384000},"page":"415-425","source":"Crossref","is-referenced-by-count":10,"title":["A 2-Approximation Algorithm for Sorting by Prefix Reversals"],"prefix":"10.1007","author":[{"given":"Johannes","family":"Fischer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simon W.","family":"Ginzinger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"2","key":"38_CR1","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/S0097539793250627","volume":"25","author":"V. Bafna","year":"1996","unstructured":"Bafna, V., Pevzner, P.A.: Genome Rearrangements and Sorting by Reversals. SIAM J. on Computing\u00a025(2), 272\u2013289 (1996)","journal-title":"SIAM J. on Computing"},{"issue":"2","key":"38_CR2","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. on Discrete Mathematics\u00a011(2), 224\u2013240 (1998)","journal-title":"SIAM J. on Discrete Mathematics"},{"key":"38_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-45749-6_21","volume-title":"Algorithms - ESA 2002","author":"P. Berman","year":"2002","unstructured":"Berman, P., Hannenhalli, S., Karpinski, M.: 1.375-Approximation Algorithm for Sorting by Reversals. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 200\u2013210. Springer, Heidelberg (2002)"},{"issue":"1","key":"38_CR4","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 J. on Discrete Mathematics\u00a012(1), 91\u2013110 (1999)","journal-title":"SIAM J. on Discrete Mathematics"},{"key":"38_CR5","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0166-218X(94)00009-3","volume":"61","author":"D.S. Cohen","year":"1995","unstructured":"Cohen, D.S., Blum, M.: On the Problem of Sorting Burnt Pancakes. Discrete Applied Mathematics\u00a061, 105\u2013120 (1995)","journal-title":"Discrete Applied Mathematics"},{"key":"38_CR6","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)"},{"key":"38_CR7","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0012-365X(79)90068-2","volume":"27","author":"W.H. Gates","year":"1979","unstructured":"Gates, W.H., Papadimitriou, C.H.: Bounds for Sorting by Prefix Reversals. Discrete Mathematics\u00a027, 47\u201357 (1979)","journal-title":"Discrete Mathematics"},{"key":"38_CR8","unstructured":"Hannehalli, S., Pevzner, P.: TO CUT ... OR NOT TO CUT (Applications of Comparative Physical Maps in Molecular Evolution). In: Proceedings of the 7th ACM Symposium on Discrete Algorithms (SODA 1996), pp. 304\u2013313 (1996)"},{"issue":"1","key":"38_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/300515.300516","volume":"46","author":"S. Hannenhalli","year":"1999","unstructured":"Hannenhalli, S., Pevzner, P.A.: Transforming Cabbage into Turnip: Polynomial Algorithm for Sorting Signed Permutations by Reversals. J. of the ACM\u00a046(1), 1\u201327 (1999)","journal-title":"J. of the ACM"},{"key":"38_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/3-540-44888-8_12","volume-title":"Combinatorial Pattern Matching","author":"T. Hartman","year":"2003","unstructured":"Hartman, T., Shamir, R.: A Simpler 1.5-Approximation Algorithms for Sorting by Transpositions. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol.\u00a02676, pp. 156\u2013169. Springer, Heidelberg (2003)"},{"key":"38_CR11","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1006\/jagm.1997.0874","volume":"25","author":"M.H. Heydari","year":"1997","unstructured":"Heydari, M.H., Sudborough, I.H.: On the Diameter of the Pancake Network. J. of Algorithms\u00a025, 67\u201394 (1997)","journal-title":"J. of Algorithms"},{"key":"38_CR12","unstructured":"Heydari, M.H.: The Pancake Problem. PhD-thesis, University of Wisconsin at Whitewater (1993)"},{"key":"38_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/3-540-58094-8_26","volume-title":"Proc. CPM 1994","author":"J. Kececioglu","year":"1994","unstructured":"Kececioglu, J., Sankoff, D.: Efficient Bounds for Oriented Chromosome Inversion Distance. In: CPM 1994. LNCS, vol.\u00a0807, pp. 307\u2013325. Springer, Heidelberg (1994)"},{"key":"38_CR14","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01188586","volume":"13","author":"J. Kececioglu","year":"1995","unstructured":"Kececioglu, J., Sankoff, D.: Exact and Approximation Algorithms for Sorting by Reversals, with Application to Genome Rearrangements. Algorithmica\u00a013, 180\u2013210 (1995)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11561071_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:13:30Z","timestamp":1619493210000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11561071_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540291183","9783540319511"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/11561071_38","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/11561071","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}