Show simple item record

dc.contributor.authorVergara, John Paul C.en
dc.date.accessioned2014-03-14T20:21:37Zen
dc.date.available2014-03-14T20:21:37Zen
dc.date.issued1997-04-08en
dc.identifier.otheretd-3156151139751001en
dc.identifier.urihttp://hdl.handle.net/10919/30401en
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.publisherVirginia Techen
dc.relation.haspartetd.pdfen
dc.relation.haspartdiss.pdfen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectnoneen
dc.titleSorting by Bounded Permutationsen
dc.typeDissertationen
dc.contributor.departmentComputer Scienceen
dc.description.degreePh. D.en
thesis.degree.namePh. D.en
thesis.degree.leveldoctoralen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.disciplineComputer Scienceen
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.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-3156151139751001/en
dc.date.sdate1998-07-12en
dc.date.rdate1997-04-08en
dc.date.adate1997-04-08en


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record