Academic Journals Database
Disseminating quality controlled scientific knowledge

Listing all sorting reversals in quadratic time

ADD TO MY LIST
 
Author(s): Swenson Krister | Badr Ghada | Sankoff David

Journal: Algorithms for Molecular Biology
ISSN 1748-7188

Volume: 6;
Issue: 1;
Start page: 11;
Date: 2011;
Original page

ABSTRACT
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.
Why do you need a reservation system?      Affiliate Program