A simpler 1.5-approximation algorithm for sorting by transpositions

DOI10.1007/3-540-44888-8_12zbMATH Open1279.68071OpenAlexW1557841343MaRDI QIDQ3550833FDOQ3550833

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

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.
• Publication:4886097

Mathematics Subject Classification ID

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

Cited In (19)

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

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)