摘要

Sorting permutations by transpositions is an important and difficult problem in genome rearrangements. The transposition diameter TD(n) is the maximum transposition distance among all pairs of permutations in S-n. It was previously conjectured [H. Eriksson et al., Discrete Math., 241 (2001), pp. 289-300] that TD(n) <= [n+1/2]. This conjecture was disproved by Elias and Hartman [IEEE/ACM Trans. Comput. Biol. Bioinform., 3 (2006), pp. 369-379] by showing TD(n) >= [n+1/2]+1. In this paper we improved the lower bound to TD(n) >= 17/33n + 1/33 via computation.

  • 出版日期2010