{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T15:46:15Z","timestamp":1772898375433,"version":"3.50.1"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2002,6,1]],"date-time":"2002-06-01T00:00:00Z","timestamp":1022889600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2002,6,1]],"date-time":"2002-06-01T00:00:00Z","timestamp":1022889600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Combinatorial Optimization"],"published-print":{"date-parts":[[2002,6]]},"DOI":"10.1023\/a:1013851611274","type":"journal-article","created":{"date-parts":[[2002,12,28]],"date-time":"2002-12-28T18:50:27Z","timestamp":1041101427000},"page":"157-182","source":"Crossref","is-referenced-by-count":17,"title":["Improved Approximation for Breakpoint Graph Decomposition and Sorting by Reversals"],"prefix":"10.1007","volume":"6","author":[{"given":"Alberto","family":"Caprara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"393733_CR1","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1137\/S0097539793250627","volume":"25","author":"V. Bafna","year":"1996","unstructured":"V. Bafna and P.A. Pevzner, \u201cGenome rearrangements and sorting by reversals,\u201d SIAM Journal on Computing, vol. 25, pp. 272\u2013289, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"393733_CR2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s002240000113","volume":"32","author":"P. Berman","year":"1999","unstructured":"P. Berman and T. Fujito, \u201cOn approximation properties of the independent set problem for low degree graphs,\u201d Theory of Computing Systems, vol. 32, pp. 115\u2013132, 1999.","journal-title":"Theory of Computing Systems"},{"key":"393733_CR3","volume-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"P. Berman","year":"1994","unstructured":"P. Berman and M. F\u00fcrer, \u201cApproximating maximum independent set in bounded degree graphs,\u201d in Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM Press: New York, 1994."},{"key":"393733_CR4","unstructured":"P. Berman and M. Karpinski, \u201cOn some tighter in approximability results,\u201d ECCC Report No. 29, University of Trier, 1998."},{"key":"393733_CR5","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1137\/S089548019731994X","volume":"12","author":"A. Caprara","year":"1999","unstructured":"A. Caprara, \u201cSorting permutations by reversals and eulerian cycle decompositions,\u201d SIAM Journal on Discrete Mathematics, vol. 12, pp. 91\u2013110, 1999a.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"393733_CR6","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1023\/A:1009838309166","volume":"3","author":"A. Caprara","year":"1999","unstructured":"A. Caprara, \u201cOn the tightness of the alternating-cycle lower bound for sorting by reversals,\u201d Journal of Combinatorial Optimization, vol. 3, pp. 149\u2013182, 1999b.","journal-title":"Journal of Combinatorial Optimization"},{"key":"393733_CR7","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A. Caprara","year":"2000","unstructured":"A. Caprara, G. Lancia, and S.K. Ng, \u201cFast practical solution of sorting by reversals,\u201d in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM Press: New York, 2000."},{"key":"393733_CR8","first-page":"244","volume-title":"Proceedings of the 9th Annual ACMSIAM Symposium on Discrete Algorithms","author":"D.A. Christie","year":"1998","unstructured":"D.A. Christie, \u201cA 3\/2 approximation algorithm for sorting by reversals,\u201d in Proceedings of the 9th Annual ACMSIAM Symposium on Discrete Algorithms, pp. 244\u2013252, ACM Press: New York, 1998."},{"key":"393733_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/300515.300516","volume":"48","author":"S. Hannenhalli","year":"1999","unstructured":"S. Hannenhalli and P.A. Pevzner, \u201cTransforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals),\u201d Journal of the ACM, vol. 48, pp. 1\u201327, 1999.","journal-title":"Journal of the ACM"},{"key":"393733_CR10","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"C.A.J. Hurkens","year":"1989","unstructured":"C.A.J. Hurkens and A. Schrijver, \u201cOn the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems,\u201d SIAM Journal on Discrete Mathematics, vol. 2, pp. 68\u201372, 1989.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"393733_CR11","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01188586","volume":"13","author":"J. Kececioglu","year":"1995","unstructured":"J. Kececioglu and D. Sankoff, \u201cExact and approximation algorithms for sorting by reversals, with application to genome rearrangement,\u201d Algorithmica, vol. 13, pp. 180\u2013210, 1995.","journal-title":"Algorithmica"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1013851611274.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1013851611274\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1013851611274.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:14:18Z","timestamp":1751282058000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1013851611274"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,6]]},"references-count":11,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2002,6]]}},"alternative-id":["393733"],"URL":"https:\/\/doi.org\/10.1023\/a:1013851611274","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,6]]}}}