Sorting by bounded block-moves

DOI10.1016/S0166-218X(98)00072-9MaRDI QIDQ1281770zbMATH OpenFDO

Authors Lenwood S. Heath, John Paul C. Vergara

Publication date 29 November 1999

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

computational biologysorting

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Computing methodologies and applications (68U99) Searching and sorting (68P10)

Recommendations

• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves
• Sorting by short block-moves
• A (1+)-approximation algorithm for sorting by short block-moves
• APPROXIMATE BLOCK SORTING
• Sorting permutations by block-interchanges

Cites work

• A priority queue in which initialization and queue operations takeO(loglogD) time
• Circular permutation graphs
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Genome Rearrangements and Sorting by Reversals
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Sorting by Transpositions
• Sorting by insertion of leading elements
• Sorting by short block-moves
• Sorting with fixed-length reversals
• The complexity of finding minimum-length generator sequences
• The minimum-length generator sequence problem is NP-hard
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(23)

• A Smooth Reshuffling Algorithm for Solving the Bulterman's Problem
• scientific article; zbMATH DE number 7765413 (Why is no real title available?)
• Sorting by prefix block-interchanges
• APPROXIMATE BLOCK SORTING
• Diameter bounds and recursive properties of Full-Flag Johnson graphs
• A (1+)-approximation algorithm for sorting by short block-moves
• An audit tool for genome rearrangement algorithms
• Approximation algorithms for sorting by bounded singleton moves
• A review of metrics on permutations for search landscape analysis
• CIRCULAR INVERSIONS OF PERMUTATIONS AND THEIR USE IN SORTING PROBLEMS
• A quadratic time 2-approximation algorithm for block sorting
• Block Sorting is Hard
• Sorting with minimum data movement
• Interchange rearrangement: the element-cost model
• Bounding prefix transposition distance for strings and permutations
• Tighter upper bound for sorting permutations with prefix transpositions
• A 14/11-approximation algorithm for sorting by short block-moves
• scientific article; zbMATH DE number 140497 (Why is no real title available?)
• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves
• On sorting by 3-bounded transpositions
• Factorization of permutations
• A new upper bound for sorting permutations with prefix transpositions
• Sorting on graphs by adjacent swaps using permutation groups

This page was built for publication: Sorting by bounded block-moves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1281770)