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$.
Type de document :
Article dans une revue
Information Processing Letters, Elsevier, 2008, 106, pp.90-95. 〈10.1016/j.ipl.2007.10.012〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00274051
Contributeur : Christophe Paul <>
Soumis le : jeudi 17 avril 2008 - 10:42:42
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

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〉

Partager

Métriques

Consultations de la notice

119