کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651451 | 1342546 | 2006 | 17 صفحه PDF | دانلود رایگان |
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⌋⌊n/2⌋ correcting skips suffice. We also present a tighter analysis of the 43 approximation algorithm of Heath and Vergara, and a possible simplification. Along the way, we study the class HnHn of those permutations of SnSn which can be sorted using correcting hops alone , and characterize large subsets of this class. We obtain a combinatorial characterization of the set Gn⊆SnGn⊆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.
Journal: Discrete Mathematics - Volume 306, Issue 14, 28 July 2006, Pages 1569–1585