title: Listing all sorting reversals in quadratic time.
abstract: We describe an average-case O(n2) algorithm to list all reversals on a signed permutation π that, when applied to π, produce a permutation that is closer to the identity. This algorithm is optimal in the sense that, the time it takes to write the list is Ω(n2) in the worst case.
authors.affiliation: Department of Mathematics and Statistics, University of Ottawa, Ontario, K1N 6N5, Canada. akswenson@uottawa.ca.
authors.forename: Krister M
authors.initials: KM
authors.lastname: Swenson
authors.forename: Ghada
authors.initials: G
authors.lastname: Badr
authors.forename: David
authors.initials: D
authors.lastname: Sankoff