Faster algorithms for sorting by transpositions and sorting by block interchanges

DOI10.1145/1273340.1273341zbMATH Open1192.68194OpenAlexW1989711785MaRDI QIDQ3580936FDOQ3580936

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

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

Mathematics Subject Classification ID

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

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)