2002 | OriginalPaper | Buchkapitel
Sorting by Prefix Transpositions
verfasst von : Zanoni Dias, João Meidanis
Erschienen in: String Processing and Information Retrieval
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A transposition is an operation that exchanges two consecutive, adjacent blocks in a permutation. A prefix transposition is a transposition that moves the first element in the permutation. In this work we present the first results on the problem of sorting permutations with the minimum number of prefix transpositions. This problem is a variation of the transposition distance problem, related to genome rearrangements. We present approximation algorithms with performance ratios of 2 and 3. We conjecture that the maximum prefix transposition distance is D(n) = n— ⌊n/4 ⌋ and present the results of several computational tests that support this. Finally, we propose an algorithm that decides whether a given permutation can be sorted using just the number of transpositions indicated by the breakpoint lower-bound.