Title page for ETD etd-3156151139751001


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

Files
  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

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

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