DocumentCode
627251
Title
The 2-approximation algorithm for sorting by prefix transposition revisited
Author
Islam, Md Shariful ; Rahman, Md Khalilur ; Rahman, Md Saifur
Author_Institution
Bangladesh Univ. of Eng. & Technol., Dhaka, Bangladesh
fYear
2013
fDate
17-18 May 2013
Firstpage
1
Lastpage
4
Abstract
A transposition is an operation that exchanges two adjacent blocks in a permutation. A prefix transposition always moves a prefix of the permutation to another location. In this article, we use a data structure, called the permutation tree, to improve the running time of the best known approximation algorithm (with approximation ratio 2) for sorting a permutation by prefix transpositions. By using the permutation tree, we improve the running time of the 2-approximation algorithm to O(n log n).
Keywords
approximation theory; computational complexity; data structures; sorting; trees (mathematics); 2-approximation algorithm; data structure; permutation prefix; permutation tree; prefix transposition; sorting; Approximation algorithms; Approximation methods; Educational institutions; Genomics; Sorting; Time complexity; Vegetation;
fLanguage
English
Publisher
ieee
Conference_Titel
Informatics, Electronics & Vision (ICIEV), 2013 International Conference on
Conference_Location
Dhaka
Print_ISBN
978-1-4799-0397-9
Type
conf
DOI
10.1109/ICIEV.2013.6572603
Filename
6572603
Link To Document