A new tight upper bound on the transposition distance

Anthony Labarre (1)

1 ULB - Université libre de Bruxelles

We study the problem of computing the minimal number of adjacent, non-intersecting block interchanges required to transform a permutation into the identity permutation. In particular, we use the graph of a permutation to compute that number for a particular class of permutations in linear time and space, and derive a new tight upper bound on the so-called transposition distance.

Domaines: Bio-informatique [q-bio.QM]; Bio-Informatique, Biologie Systémique [q-bio.QM]

Anthony Labarre. A new tight upper bound on the transposition distance. Workshop on Algorithms in Bioinformatics (WABI), Sep 2005, Spain. pp.216-227, ⟨10.1007/11557067_18⟩. ⟨hal-00728796⟩