A 1.375-Approximation Algorithm for Sorting by Transpositions
Citations Over TimeTop 10% of 2006 papers
Abstract
Sorting permutations by transpositions is an important problem in genome rearrangements. A transposition is a rearrangement operation in which a segment is cut out of the permutation and pasted in a different location. The complexity of this problem is still open and it has been a 10-year-old open problem to improve the best known 1.5-approximation algorithm. In this paper, we provide a 1.375-approximation algorithm for sorting by transpositions. The algorithm is based on a new upper bound on the diameter of 3-permutations. In addition, we present some new results regarding the transposition diameter: we improve the lower bound for the transposition diameter of the symmetric group and determine the exact transposition diameter of simple permutations.
Related Papers
- → Transposition of teeth(1979)37 cited
- → The structure of didactic transposition capability - analysis of an example of didactic transposition of physical knowledge in the training of pedagogical students(2020)1 cited
- Study on Electric Imbalance and Transposition of 750 kV 1-Tower Double-Circuit Transmission Line(2007)
- Optimization of Conductor Transposition and Configuration of Insulated Ground Wire on Overhead Transmission Line(2000)
- → Gantry Transposition to Reduce Unbalance Phenomena in Long Transmission and Small Loading Substations in Central Kalimantan(2021)