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

- none
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

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.

Files

Filename Size Approximate Download Time (Hours:Minutes:Seconds)

28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access diss.pdf1.38 Mb 00:06:23 00:03:17 00:02:52 00:01:26 00:00:07 etd.pdf1.38 Mb 00:06:23 00:03:17 00:02:52 00:01:26 00:00:07

Browse All Available ETDs by
( Author |
Department )

If you have questions or technical problems, please Contact DLA.