TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 26.06.2014


Page Content

to Navigation

Reversal Distances for Strings with Few Blocks or Small Alphabets

Dr. Laurent Bulteau (TU Berlin)

We study the String Reversal Distance problem, an extension of the well-known genomer rearrangement problem Sorting by Reversals. String Reversal Distance takes two strings S and T as input, and asks for a minimum number of reversals to obtain T from S. We also consider variants: String Prefix Reversal Distance (in which any reversal must include the first letter of the string), and the signed variant (where elements have orientations). We study algorithmic properties of these four problems, in connection with two parameters of the input strings: the number of blocks they contain (a block being maximal substring such that all letters in the substring are equal), and the alphabet size. For instance, we show that Signed String Reversal Distance is NP-hard even if on unary alphabets.

26.06.2014 16:15
Laurent Bulteau
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe