Title: A new tight upper bound on the transposition distance
Authors: Labarre, Anthony #
Issue Date: Oct-2005
Publisher: Springer-Verlag
Host Document: Fifth Workshop on Algorithms in Bioinformatics (WABI) vol:3692 pages:216-227
Conference: Workshop on Algorithms in Bioinformatics edition:5 location:Palma de Mallorca, Spain date:3-6 October 2005
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.
ISSN: 0302-9743
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Informatics Section
# (joint) last author

Files in This Item:
File Description Status SizeFormat
wabi2005.pdfMain article Published 555KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science