Listing all sorting reversals in quadratic time

Description
Title: Listing all sorting reversals in quadratic time
Authors: Swenson, Krister M
Badr, Ghada
Sankoff, David
Date: 2011-04-19
Abstract: Abstract We describe an average-case O(n 2) 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 Ω(n 2) in the worst case.
URL: http://dx.doi.org/10.1186/1748-7188-6-11
http://hdl.handle.net/10393/33560
CollectionLibre accès - Publications // Open Access - Publications
Files