Type of Document Dissertation Author Vergara, John Paul C. URN etd-3156151139751001 Title Sorting by Bounded Permutations Degree PhD Department Computer Science Advisory Committee
Advisor Name Title Allison, Donald C. S. Brown, Ezra A. Green, Edward L. Shaffer, Clifford A. Heath, Lenwood S. Committee Chair Keywords
Date of Defense 1997-04-08 Availability unrestricted 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
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
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.
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access diss.pdf 1.38 Mb 00:06:23 00:03:17 00:02:52 00:01:26 00:00:07 etd.pdf 1.38 Mb 00:06:23 00:03:17 00:02:52 00:01:26 00:00:07
If you have questions or technical problems, please Contact DLA.