Faster algorithms for sorting by transpositions and sorting by block interchanges

DOI10.1145/1273340.1273341MaRDI QIDQ3580936zbMATH OpenOpenAlexFDO

Authors Jianxing Feng, Daming Zhu

Publication date 14 August 2010

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1273340.1273341

Mathematics Subject Classification ID

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

Recommendations

• Theory and Applications of Models of Computation
• The 1.375 approximation algorithm for sorting by transpositions can run in \(O(n\log n)\) time
• A simpler and faster 1.5-approximation algorithm for sorting by transpositions
• An improved block-interchange algorithm
• An improved algorithm for sorting by block-interchanges based on permutation groups

Cited in

(14)

• Fast Intersection Algorithms for Sorted Sequences
• An improved block-interchange algorithm
• Theory and Applications of Models of Computation
• A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations
• \(\log\)-lists and their applications to sorting by transpositions, reversals and block-interchanges
• Approximation algorithms for sorting by bounded singleton moves
• CIRCULAR INVERSIONS OF PERMUTATIONS AND THEIR USE IN SORTING PROBLEMS
• An improved algorithm for sorting by block-interchanges based on permutation groups
• A New and Faster Method of Sorting by Transpositions
• The 1.375 approximation algorithm for sorting by transpositions can run in \(O(n\log n)\) time
• Approximation algorithms for sorting permutations by extreme block-interchanges
• Block Sorting Is APX-Hard
• Sorting on graphs by adjacent swaps using permutation groups
• Constant time and space updates for the sigma-tau problem

This page was built for publication: Faster algorithms for sorting by transpositions and sorting by block interchanges

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