Sorting by Bounded Permutations

dc.contributor.authorVergara, John Paul C.en
dc.contributor.committeechairHeath, Lenwood S.en
dc.contributor.committeememberAllison, Donald C. S.en
dc.contributor.committeememberGreen, Edward L.en
dc.contributor.committeememberBrown, Ezra A.en
dc.contributor.committeememberShaffer, Clifford A.en
dc.contributor.departmentComputer Scienceen
dc.description.abstractLet 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.degreePh. D.en
dc.publisherVirginia Techen
dc.rightsIn Copyrighten
dc.titleSorting by Bounded Permutationsen
dc.typeDissertationen Scienceen Polytechnic Institute and State Universityen D.en


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
1.32 MB
Adobe Portable Document Format