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)

Full work available at URL https://doi.org/10.1016/S0166-218X(98)00072-9

zbMATH Keywords

computational biologysorting

Mathematics Subject Classification ID

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

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 by insertion of leading elements
• Sorting by short block-moves
• Sorting by Transpositions
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• 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

(24)

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

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)