A More Efficient Algorithm for Perfect Sorting by Reversals - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Information Processing Letters Year : 2008

A More Efficient Algorithm for Perfect Sorting by Reversals

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$.

Dates and versions

lirmm-00274051 , version 1 (17-04-2008)

Identifiers

Cite

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

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More