{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:11:45Z","timestamp":1784110305124,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540441809","type":"print"},{"value":"9783540457497","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45749-6_21","type":"book-chapter","created":{"date-parts":[[2007,7,4]],"date-time":"2007-07-04T11:42:44Z","timestamp":1183549364000},"page":"200-210","source":"Crossref","is-referenced-by-count":69,"title":["1.375-Approximation Algorithm for Sorting by Reversals"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sridhar","family":"Hannenhalli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,8,29]]},"reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1016\/0196-6774(89)90037-0","volume":"10","author":"N. Amato","year":"1989","unstructured":"N. Amato, M. Blum, S. Irani and R. Rubinfeld, Reversing Trains: a turn of the century sorting problem, J. of Algorithms 10:413\u2013428, 1989.","journal-title":"J. of Algorithms"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"V. Bafna and P. Pevzner, Genome rearrangements and sorting by reversals, Proc. of 34th IEEE FOCS, 148\u2013157, 1993; also in SIAM J. on Computing 25:272\u2013289, 1996.","DOI":"10.1137\/S0097539793250627"},{"key":"21_CR3","unstructured":"P. Berman and M. F\u00fcrer, Approximating independent set problem in bounded degree graphs, Proc. SODA 1994, 365\u2013371."},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"P. Berman and S. Hannenhalli, Fast Sorting by Reversals, Proc. of 7th CPM, 168\u2013185, 1996.","DOI":"10.1007\/3-540-61258-0_14"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"P. Berman and M. Karpinski, On some tighter inapproximability results, Proc. of 26th ICALP, LNCS 1644:200\u2013209, Springer-Verlag, Berlin, 1999.","DOI":"10.1007\/3-540-48523-6_17"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"A. Caprara, Sorting by Reversals is difficult, Proc. of 1st ACM RECOMB, 75\u201383, 1997, to appear in SIAM J. of Discr. Math. 2001.","DOI":"10.1145\/267521.267531"},{"key":"21_CR7","unstructured":"D.A. Christie, A 3\/2 Approximation algorithm for sorting by reversals, Proc. of 9th ACM-SIAM SODA, 244\u2013252, 1998."},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0166-218X(94)00009-3","volume":"61","author":"D. Cohen","year":"1995","unstructured":"D. Cohen and M. Blum, On the problem of Sorting Burnt Pancakes, Discrete Appl. Math. 61:105\u2013125, 1995.","journal-title":"Discrete Appl. Math."},{"key":"21_CR9","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0012-365X(79)90068-2","volume":"27","author":"W.H. Gates","year":"1979","unstructured":"W.H. Gates and C.H. Papadimitriou, Bounds for sorting by pre.x reversals, Discr. Math. 27:47\u201357, 1979.","journal-title":"Discr. Math."},{"key":"21_CR10","unstructured":"M. M. Halld\u00f3rsson and K. Yoshikara, Greedy approximation of independent sets in low degree graphs"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"S. Hannenhalli and P. Pevzner, Transforming cabbage into turnip, Proc. of 27th ACM STOC 1995, 178\u2013189.","DOI":"10.1145\/225058.225112"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"S. Hannenhalli and P. Pevzner, To cut... or not to cut, Proc. of 7th ACMSIAM SODA 1996, 304\u2013313.","DOI":"10.1136\/bmj.313.7048.7a"},{"issue":"1","key":"21_CR13","first-page":"62","volume":"2","author":"C. A. J. Hurkens","year":"1989","unstructured":"C. A. J. Hurkens and A. Schcrijver, On the size of systems of sets every t of which have an SDR, with an aplication to the worst case ratio of heuristic for Packing Problem, SIAM J. of Discr. Math. 2(1):62\u201372, 1989.","journal-title":"SIAM J. of Discr. Math."},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"H. Kaplan, R. Shamir and R.E. Tarjan, Faster and simpler algorithm for sorting signed permutations by reversals, Proc. of 8th ACM-SIAM SODA, 178\u2013187, 1997.","DOI":"10.1145\/267521.267544"},{"key":"21_CR15","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01188586","volume":"13","author":"J. Kececioglu","year":"1995","unstructured":"J. Kececioglu and D. Sanko., Exact and approximation algorithms for the inversion distance between two permutations, Algorithmica 13:180\u2013210, 1995.","journal-title":"Algorithmica"},{"key":"21_CR16","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2022.001.0001","volume-title":"Computational Molecular Biology-An Algorithmic Approach","author":"P. Pevzner","year":"2000","unstructured":"P. Pevzner, Computational Molecular Biology-An Algorithmic Approach, The MIT Press, Cambridge, 2000."},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"D. Sanko., R. Cedergen and Y. Abel, Genomic divergence through gene rearrangement, in Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences, chapter 26, 428\u2013238, Academic Press, 1990.","DOI":"10.1016\/0076-6879(90)83028-8"},{"key":"21_CR18","first-page":"6575","volume":"89","author":"D. Sanko","year":"1992","unstructured":"D. Sanko., G. Leduc, N. Antoine, B. Paquin, B. F. Lang and R. Cedergen, Gene order comparisons for phylogenetic inference: Evolution of the mitochondrial genome, Proc. Natl. Acad. Sci. USA, 89:6575\u20136579, 1992.","journal-title":"Gene order comparisons for phylogenetic inference: Evolution of the mitochondrial genome"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45749-6_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T23:06:16Z","timestamp":1556579176000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45749-6_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441809","9783540457497"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-45749-6_21","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}