Sorting by Bounded Permutations
| dc.contributor.author | Vergara, John Paul C. | en |
| dc.contributor.committeechair | Heath, Lenwood S. | en |
| dc.contributor.committeemember | Allison, Donald C. S. | en |
| dc.contributor.committeemember | Green, Edward L. | en |
| dc.contributor.committeemember | Brown, Ezra A. | en |
| dc.contributor.committeemember | Shaffer, Clifford A. | en |
| dc.contributor.department | Computer Science | en |
| dc.date.accessioned | 2014-03-14T20:21:37Z | en |
| dc.date.adate | 1997-04-08 | en |
| dc.date.available | 2014-03-14T20:21:37Z | en |
| dc.date.issued | 1997-04-08 | en |
| dc.date.rdate | 1997-04-08 | en |
| dc.date.sdate | 1998-07-12 | en |
| dc.description.abstract | Let P be a predicate applicable to permutations. A permutation that satisfies P is called a generator. Given a permutation $pi$, MinSort_P is the problem of finding a shortest sequence of generators that, when composed with $pi$, yields the identity permutation. The length of this sequence is called the P distance of $pi$. Diam_P is the problem of finding the longest such distance for permutations of a given length. MinSort_P and Diam_P, for some choices of P, have applications in the study of genome rearrangements and in the design of interconnection networks. This dissertation considers generators that are swaps, reversals, or block-moves. Distance bounds on these generators are introduced and the corresponding problems are investigated. Reduction results, graph-theoretic models, exact and approximation algorithms, and heuristics for these problems are presented. Experimental results on the heuristics are also provided. When the bound is a function of the length of the permutation, there are several sorting problems such as sorting by block-moves and sorting by reversals whose bounded variants are at least as difficult as the corresponding unbounded problems. For some bounded problems, a strong relationship exists between finding optimal sorting sequences and correcting the relative order of individual pairs of elements. This fact is used in investigating MinSort_P and Diam_P for two particular predicates. A short block-move is a generator that moves an element at most two positions away from its original position. Sorting by short block-moves is solvable in polynomial time for two large classes of permutations: woven bitonic permutations and woven double-strip permutations. For general permutations, a polynomial-time (4/3)-approximation algorithm that computes short block-move distance is devised. The short block-move diameter for length-n permutations is determined. A short swap is a generator that swaps two elements that have at most one element between them. A polynomial-time 2-approximation algorithm for computing short swap distance is devised and a class of permutations where the algorithm computes the exact short swap distance is determined. Bounds for the short swap diameter for length-n permutations are determined. | en |
| dc.description.degree | Ph. D. | en |
| dc.identifier.other | etd-3156151139751001 | en |
| dc.identifier.sourceurl | http://scholar.lib.vt.edu/theses/available/etd-3156151139751001/ | en |
| dc.identifier.uri | http://hdl.handle.net/10919/30401 | en |
| dc.publisher | Virginia Tech | en |
| dc.relation.haspart | etd.pdf | en |
| dc.relation.haspart | diss.pdf | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject | none | en |
| dc.title | Sorting by Bounded Permutations | en |
| dc.type | Dissertation | en |
| thesis.degree.discipline | Computer Science | en |
| thesis.degree.grantor | Virginia Polytechnic Institute and State University | en |
| thesis.degree.level | doctoral | en |
| thesis.degree.name | Ph. D. | en |
Files
Original bundle
1 - 1 of 1