The 1.375 approximation algorithm for sorting by transpositions can run in O(n n) time

DOI10.1007/978-3-642-11440-3_15zbMATH Open1274.68686OpenAlexW2083245516MaRDI QIDQ3404440FDOQ3404440

Authors: Jesun S. Firoz, Masud Hasan, Ashik Z. Khan, M. Sohel Rahman 

Publication date: 9 February 2010

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11440-3_15

Recommendations

• Theory and Applications of Models of Computation
• Faster algorithms for sorting by transpositions and sorting by block interchanges
• A simpler and faster 1.5-approximation algorithm for sorting by transpositions
• A simpler 1.5-approximation algorithm for sorting by transpositions
• An $O(n^{3/2}\sqrt{\log (n)})$ Algorithm for Sorting by Reciprocal Translocations

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Approximation algorithms (68W25)

Cited In (7)

• Faster algorithms for sorting by transpositions and sorting by block interchanges
• Theory and Applications of Models of Computation
• 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
• Data Exchange and Permutation Length
• Zig-zag sort
• On sorting by 3-bounded transpositions

This page was built for publication: The 1.375 approximation algorithm for sorting by transpositions can run in \(O(n\log n)\) time

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