TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 26.06.2014

isti-logo

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.

Date
Speaker
Location
Language
26.06.2014 16:15
Laurent Bulteau
TEL 512
english

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe