A simpler and faster 1.5-approximation algorithm for sorting by transpositions
From MaRDI portal
Publication:2490115
DOI10.1016/j.ic.2005.09.002zbMath1092.68580OpenAlexW2047742824MaRDI QIDQ2490115
Publication date: 28 April 2006
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2005.09.002
Related Items (9)
Block crossings in one-sided tanglegrams ⋮ The transposition median problem is NP-complete ⋮ Sorting permutations with transpositions in \(O(n^3)\) amortized time ⋮ CIRCULAR INVERSIONS OF PERMUTATIONS AND THEIR USE IN SORTING PROBLEMS ⋮ Tighter upper bound for sorting permutations with prefix transpositions ⋮ Sorting by Transpositions Is Difficult ⋮ \(\log\)-lists and their applications to sorting by transpositions, reversals and block-interchanges ⋮ Bounding prefix transposition distance for strings and permutations ⋮ The complexity of string partitioning
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A 2-approximation algorithm for genome rearrangements by reversals and transpositions
- Transforming cabbage into turnip
- A Simpler 1.5-Approximation Algorithm for Sorting by Transpositions
- Efficient Data Structures and a New Randomized Approach for Sorting Signed Permutations by Reversals
- Working on the Problem of Sorting by Transpositions on Genome Rearrangements
- Self-adjusting binary search trees
- Sorting Permutations by Reversals and Eulerian Cycle Decompositions
- Sorting by Transpositions
- Genome Rearrangements and Sorting by Reversals
- A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
- Signed genome rearrangement by reversals and transpositions: Models and approximations
- Sorting a bridge hand
This page was built for publication: A simpler and faster 1.5-approximation algorithm for sorting by transpositions
