\((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.
From MaRDI portal
Publication:1853543
DOI10.1016/S0304-3975(01)00338-3zbMath1061.68038MaRDI QIDQ1853543
Publication date: 21 January 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
68P10: Searching and sorting
05A05: Permutations, words, matrices
90C27: Combinatorial optimization
92D20: Protein sequences, DNA sequences
Related Items
APPROXIMATE BLOCK SORTING, Pancake flipping and sorting permutations, The transposition median problem is NP-complete, The mathematics of lecture hall partitions, Expected number of breakpoints after \(t\) random reversals in genomes with duplicate genes, An approximation algorithm for sorting by reversals and transpositions, Reversal and transposition medians, Length-weighted \(\lambda\)-rearrangement distance, The complexity of string partitioning, On sorting by 3-bounded transpositions
Cites Work