A simpler 1.5-approximation algorithm for sorting by transpositions

DOI10.1007/3-540-44888-8_12MaRDI QIDQ3550833zbMATHOpenAlexFDO

Authors Tzvika Hartman

Publication date 6 April 2010

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-44888-8_12

Mathematics Subject Classification ID

Searching and sorting (68P10) Approximation algorithms (68W25)

Recommendations

• A simpler and faster 1.5-approximation algorithm for sorting by transpositions
• An approximation algorithm for sorting by reversals and transpositions
• (1+ε)-Approximation of Sorting by Reversals and Transpositions
• \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.
• scientific article; zbMATH DE number 910920

Cited in

(20)

• A review of metrics on permutations for search landscape analysis
• Pancake flipping and sorting permutations
• A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations
• On sorting by 3-bounded transpositions
• An approximation algorithm for sorting by reversals and transpositions
• Sorting signed permutations by reversals, revisited
• Sorting by shuffling methods and a queue
• Improving the algorithm of Bafna and Pevzner for the problem of sorting by transpositions: a practical approach
• Sorting by shuffling methods and a queue
• CIRCULAR INVERSIONS OF PERMUTATIONS AND THEIR USE IN SORTING PROBLEMS
• Multi-break rearrangements and chromosomal evolution
• A new approximation algorithm for unsigned translocation sorting
• A New and Faster Method of Sorting by Transpositions
• A 2.25-Approximation Algorithm for Cut-and-Paste Sorting of Unsigned Circular Permutations
• Short proofs for cut-and-paste sorting of permutations
• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves
• The 1.375 approximation algorithm for sorting by transpositions can run in \(O(n\log n)\) time
• A 14/11-approximation algorithm for sorting by short block-moves
• A simpler and faster 1.5-approximation algorithm for sorting by transpositions
• \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.

This page was built for publication: A simpler 1.5-approximation algorithm for sorting by transpositions

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