1. A Practical Exponential-Time Algorithm on Sorting by Short Block-Moves
- Author
-
Da-Ming Zhu, Qingsong Xie, Hui Fan, Jinjie Xiao, Pei-Qiang Liu, and Hai Yan Zhu
- Subjects
Set (abstract data type) ,Sorting algorithm ,Theoretical computer science ,Computational complexity theory ,Sorting ,Approximation algorithm ,Algorithm ,Exponential function ,Block (data storage) ,Mathematics ,Test data - Abstract
Sorting by short block-moves is one of the several approaches recently used for genome rearrangement, and most of the minimum sorting questions by these approaches have been proved to be NP-complete or NP-hard or even PSPACE-complete. Nevertheless, the complexity of minimum sorting by block-moves remains unsolved, and approximation algorithms for it and polynomial-time algorithms on special permutations for it are continuously devised. This paper gives an exponential-time algorithm of minimum sorting by short block-moves, and verifies its practicability by a set of test data.
- Published
- 2009
- Full Text
- View/download PDF