Skip to Main content Skip to Navigation
Journal articles

A More Efficient Algorithm for Perfect Sorting by Reversals

Sèverine Bérard 1 Cedric Chauve 2 Christophe Paul 3
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We describe a new algorithm for the problem of perfect sorting a signed permutation by reversals. The worst-case time complexity of this algorithm is parameterized by the maximum prime degree $d$ of the strong interval tree, i.e. $f(d).n^{O(1)}$. This improves the best known algorithm which complexity was based on a parameter always larger than or equal to $d$.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00274051
Contributor : Christophe Paul <>
Submitted on : Thursday, April 17, 2008 - 10:42:42 AM
Last modification on : Sunday, May 31, 2020 - 3:29:08 AM

Links full text

Identifiers

Collections

Citation

Sèverine Bérard, Cedric Chauve, Christophe Paul. A More Efficient Algorithm for Perfect Sorting by Reversals. Information Processing Letters, Elsevier, 2008, 106, pp.90-95. ⟨10.1016/j.ipl.2007.10.012⟩. ⟨lirmm-00274051⟩

Share

Metrics

Record views

286