Please use this identifier to cite or link to this item:
Type: Artigo de evento
Title: On Sorting Of Signed Permutations By Prefix And Suffix Reversals And Transpositions
Author: Lintzmayer C.N.
Dias Z.
Abstract: A reversal inverts a segment and the signs of the elements of this segment in a permutation. A transposition exchanges the position of two consecutive segments. These are the most common kinds of genome rearrangements. In this paper, we introduce the study of prefix and suffix versions of these operations, that is, when only segments of the beginning or of the end are involved, when considering signed permutations. We gave asymptotic approximation algorithms of factor two for three new problems: when prefix and suffix reversals are allowed, when prefix reversals and prefix transpositions are allowed, and when prefix and suffix reversals and prefix and suffix transpositions are allowed. © 2014 Springer International Publishing.
Editor: Springer Verlag
Rights: fechado
Identifier DOI: 10.1007/978-3-319-07953-0_12
Date Issue: 2014
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-84903993807.pdf250.89 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.