 |
HAL UPEC - UPEM Portal |  |
 |
Conference papers
A new tight upper bound on the transposition distance
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.
Cited literature [14 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-00728796
Contributor : Anthony Labarre Connect in order to contact the contributor
Submitted on : Thursday, September 6, 2012 - 4:19:25 PM
Last modification on : Tuesday, October 19, 2021 - 12:55:33 PM
Long-term archiving on: : Friday, December 7, 2012 - 3:42:48 AM
Contributor : Anthony Labarre Connect in order to contact the contributor
Submitted on : Thursday, September 6, 2012 - 4:19:25 PM
Last modification on : Tuesday, October 19, 2021 - 12:55:33 PM
Long-term archiving on: : Friday, December 7, 2012 - 3:42:48 AM
File
wabi2005.pdf
Publisher files allowed on an open archive