Header menu link for other important links
X
On sorting by 3-bounded transpositions
Published in
2006
Volume: 306
   
Issue: 14
Pages: 1569 - 1585
Abstract
Heath and Vergara [Sorting by short block moves, Algorithmica 28 (2000) 323-352] proved the equivalence between sorting by 3-bounded transpositions and sorting by correcting skips and correcting hops. This paper explores various algorithmic as well as combinatorial aspects of correcting skips/hops, with the aim of understanding 3-bounded transpositions better. We show that to sort any permutation via correcting hops and skips, ⌊ n / 2 ⌋ correcting skips suffice. We also present a tighter analysis of the frac(4, 3) approximation algorithm of Heath and Vergara, and a possible simplification. Along the way, we study the class Hn of those permutations of Sn which can be sorted using correcting hops alone, and characterize large subsets of this class. We obtain a combinatorial characterization of the set Gn ⊆ Sn of all correcting-hop-free permutations, and describe a linear-time algorithm to optimally sort such permutations. We also show how to efficiently sort a permutation with a minimum number of correcting moves. © 2006 Elsevier B.V. All rights reserved.
About the journal
JournalDiscrete Mathematics
ISSN0012365X
Open AccessYes
Concepts (11)
  •  related image
    Approximation theory
  •  related image
    Combinatorial mathematics
  •  related image
    Genes
  •  related image
    Linear equations
  •  related image
    Numerical methods
  •  related image
    Sorting
  •  related image
    Approximation algorithms
  •  related image
    BOUNDED TRANSPOSITIONS
  •  related image
    GENOME REARRANGEMENT
  •  related image
    LINEAR-TIME ALGORITHM
  •  related image
    Algorithms