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

DOI10.1007/978-3-642-11440-3_15MaRDI QIDQ3404440zbMATHOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(7)

• A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations
• On sorting by 3-bounded transpositions
• Theory and Applications of Models of Computation
• Zig-zag sort
• Data Exchange and Permutation Length
• Faster algorithms for sorting by transpositions and sorting by block interchanges
• A simpler and faster 1.5-approximation algorithm for sorting by 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)