A faster and simpler algorithm for sorting signed permutations by reversals

Authors
Kaplan, H Shamir, R Tarjan, RE
Citation
H. Kaplan et al., A faster and simpler algorithm for sorting signed permutations by reversals, SIAM J COMP, 29(3), 2000, pp. 880-892
Citations number
26
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
00975397 → ACNP
Volume
29
Issue
3
Year of publication
2000
Pages
880 - 892
Database
ISI
SICI code
0097-5397(20000112)29:3<880:AFASAF>2.0.ZU;2-D
Abstract
We give a quadratic time algorithm for finding the minimum number of revers als needed to sort a signed permutation. Our algorithm is faster than the p revious algorithm of Hannenhalli and Pevzner and its faster implementation by Berman and Hannenhalli. The algorithm is conceptually simple and does no t require special data structures. Our study also considerably simplifies t he combinatorial structures used by the analysis.