Publications

Abstract : A reversal is an operation that reverses a substring. When the chosen substring is restricted to a prefix it is called a prefix reversal. Given two strings, α and β, the problem of finding the minimum number of prefix reversals that transform α into β is called the prefix reversal distance problem. This problem is a version of the reversal distance problem, related to genetic rearrangements. An upper bound of 18n/11 and a lower bound of 15n/14 are known for permutations. We give bounds for prefix reversals on strings. For example, n-1 prefix reversals are sufficient to transform a given n-binary string into a compatible string, i.e. a string with same frequency for each symbol as the given string. We also prove that the prefix reversal distance for strings is NP-complete.