Inhalt des Dokuments
Es gibt keine deutsche Übersetzung dieser Webseite.
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.
Date | Speaker | Location | Language |
---|---|---|---|
26.06.2014 16:15 | Laurent Bulteau | TEL 512 | english |