Sorting by Short Block-Moves
| dc.contributor.author | Heath, Lenwood S. | en |
| dc.contributor.author | Vergara, John Paul C. | en |
| dc.contributor.department | Computer Science | en |
| dc.date.accessioned | 2013-06-19T14:36:07Z | en |
| dc.date.available | 2013-06-19T14:36:07Z | en |
| dc.date.issued | 1998-02-01 | en |
| dc.description.abstract | Sorting permutations by operations such as reversals and block-moves has received much interest because of its applications in computational biology, particularly in the study of genome rearrangements. A short block-move is an operation on a permutation that moves an element at most two positions away from its original position. This paper investigates the problem of finding a minimum-length sorting sequence of short block-moves for a given permutation. A 4/3-approximation algorithm for this problem is presented. Exact polynomial-time algorithms are presented for woven bitonic permutations and woven double-strip permutations. A linear-time maximum matching algorithm for a special class of grid graphs is also discovered that improves the time complexity of one of these exact algorithms. | en |
| dc.format.mimetype | application/postscript | en |
| dc.identifier | http://eprints.cs.vt.edu/archive/00000482/ | en |
| dc.identifier.sourceurl | http://eprints.cs.vt.edu/archive/00000482/01/TR-98-03.ps | en |
| dc.identifier.trnumber | TR-98-03 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/19985 | en |
| dc.language.iso | en | en |
| dc.publisher | Department of Computer Science, Virginia Polytechnic Institute & State University | en |
| dc.relation.ispartof | Historical Collection(Till Dec 2001) | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.title | Sorting by Short Block-Moves | en |
| dc.type | Technical report | en |
| dc.type.dcmitype | Text | en |
Files
Original bundle
1 - 1 of 1