\((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.

DOI10.1016/S0304-3975(01)00338-3zbMath1061.68038MaRDI QIDQ1853543

Niklas Eriksen

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Approximation algorithmSortingPermutationsGenome rearrangementsReversalsTranspositions

Mathematics Subject Classification ID

Searching and sorting (68P10) Permutations, words, matrices (05A05) Combinatorial optimization (90C27) Protein sequences, DNA sequences (92D20)

Related Items (10)

APPROXIMATE BLOCK SORTING ⋮ The transposition median problem is NP-complete ⋮ Pancake flipping and sorting permutations ⋮ Expected number of breakpoints after \(t\) random reversals in genomes with duplicate genes ⋮ On sorting by 3-bounded transpositions ⋮ Length-weighted \(\lambda\)-rearrangement distance ⋮ The mathematics of lecture hall partitions ⋮ An approximation algorithm for sorting by reversals and transpositions ⋮ Reversal and transposition medians ⋮ The complexity of string partitioning

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 2-approximation algorithm for genome rearrangements by reversals and transpositions
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Sorting by Transpositions
• Genome Rearrangements and Sorting by Reversals

This page was built for publication: \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.