Sorting by bounded block-moves

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)

zbMATH Keywords

sortingcomputational biology

Mathematics Subject Classification ID

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