Skip to Main content Skip to Navigation
Conference papers

A new tight upper bound on the transposition distance

Anthony Labarre 1, *
Abstract : 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.
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00728796
Contributor : Anthony Labarre <>
Submitted on : Thursday, September 6, 2012 - 4:19:25 PM
Last modification on : Thursday, June 4, 2020 - 10:24:03 AM
Long-term archiving on: : Friday, December 7, 2012 - 3:42:48 AM

File

wabi2005.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

288

Files downloads

225