Sorting by bounded block-moves
From MaRDI portal
Publication:1281770
DOI10.1016/S0166-218X(98)00072-9zbMath0927.68024MaRDI QIDQ1281770
Lenwood S. Heath, John Paul C. Vergara
Publication date: 29 November 1999
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Searching and sorting (68P10) Permutations, words, matrices (05A05) Computing methodologies and applications (68U99)
Related Items (17)
APPROXIMATE BLOCK SORTING ⋮ Sorting on graphs by adjacent swaps using permutation groups ⋮ Approximation algorithms for sorting by bounded singleton moves ⋮ A review of metrics on permutations for search landscape analysis ⋮ An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves ⋮ A \((1+\varepsilon)\)-approximation algorithm for sorting by short block-moves ⋮ Block Sorting is Hard ⋮ CIRCULAR INVERSIONS OF PERMUTATIONS AND THEIR USE IN SORTING PROBLEMS ⋮ Tighter upper bound for sorting permutations with prefix transpositions ⋮ Diameter bounds and recursive properties of Full-Flag Johnson graphs ⋮ A 14/11-approximation algorithm for sorting by short block-moves ⋮ On sorting by 3-bounded transpositions ⋮ Interchange rearrangement: the element-cost model ⋮ A quadratic time 2-approximation algorithm for block sorting ⋮ An Audit Tool for Genome Rearrangement Algorithms ⋮ Bounding prefix transposition distance for strings and permutations ⋮ A new upper bound for sorting permutations with prefix transpositions
Cites Work
- The complexity of finding minimum-length generator sequences
- Sorting by insertion of leading elements
- Sorting by short block-moves
- Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
- A priority queue in which initialization and queue operations takeO(loglogD) time
- The minimum-length generator sequence problem is NP-hard
- Sorting Permutations by Reversals and Eulerian Cycle Decompositions
- Sorting by Transpositions
- Circular permutation graphs
- Genome Rearrangements and Sorting by Reversals
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- Sorting with fixed-length reversals
This page was built for publication: Sorting by bounded block-moves
