Faster and simpler algorithm for sorting signed permutations by reversals

Haim Kaplan, Ron Shamir, Robert E. Tarjan

Research output: Contribution to conferencePaper

3 Scopus citations

Abstract

We give a quadratic algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its faster implementation of Berman and Hannenhalli. The algorithm is conceptually simple and does not require special data structures. Our study also considerably simplifies the combinatorial structures used by the analysis.

Original languageEnglish (US)
Number of pages1
DOIs
StatePublished - 1997
EventProceedings of the 1997 1st Annual International Conference on Computational Molecular Biology, RECOMB - Santa Fe, NM, USA
Duration: Jan 20 1997Jan 23 1997

Other

OtherProceedings of the 1997 1st Annual International Conference on Computational Molecular Biology, RECOMB
CitySanta Fe, NM, USA
Period1/20/971/23/97

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Faster and simpler algorithm for sorting signed permutations by reversals'. Together they form a unique fingerprint.

  • Cite this

    Kaplan, H., Shamir, R., & Tarjan, R. E. (1997). Faster and simpler algorithm for sorting signed permutations by reversals. Paper presented at Proceedings of the 1997 1st Annual International Conference on Computational Molecular Biology, RECOMB, Santa Fe, NM, USA, . https://doi.org/10.1145/267521.267544