Sign in
Back
The 1.375 Approximation Algorithm for Sorting by Transpositions Can Run in $O(n\log n)$ Time
Other

The 1.375 Approximation Algorithm for Sorting by Transpositions Can Run in $O(n\log n)$ Time

Jesun Sahariar Firoz, Masud Hasan, Ashik Zinnat Khan and M. Sohel Rahman
17/10/2009

Abstract

Algorithms Computer Science Data Structures Discrete Mathematics
Sorting a Permutation by Transpositions (SPbT) is an important problem in Bioinformtics. In this paper, we improve the running time of the best known approximation algorithm for SPbT. We use the permutation tree data structure of Feng and Zhu and improve the running time of the 1.375 Approximation Algorithm for SPbT of Elias and Hartman to $O(n\log n)$. The previous running time of EH algorithm was $O(n^2)$.

Metrics

1 Record Views

Details