Sven Thiel (Friedrich-Schiller-Universität Jena)
Der Vortrag gibt einen Überblick über das Graphmodifikationsproblem Consistent Cut. Als Eingabe dient ein ungerichteter k-gefärbter Graph sowie eine natürliche Zahl l. Dabei entspricht k der Anzahl der Farben des Graphen. Die Frage ist ob eine Menge von Kantenlöschungen für den Graphen der Größe höchstens l existiert, so dass jede Zusammenhangskomponente höchstens einen Knoten jeder Farbe beinhaltet. Es wird gezeigt, dass Consistent Cut für das bioinformatisch relevante Problem der multiplen Sequenzalignments (MSA) anwendbar ist. Außerdem wird sowohl die klassische als auch die parametrisierte Komplexität von Consistent Cut vorgestellt. Dabei wird gezeigt, dass das Problem NP-hart sowie festparameter-handhabbar bezüglich des kombinierten Parameters (k, l) ist. Darüber hinaus werden einige Datenreduktionsregeln vorgestellt und Spezialfälle des Problems betrachtet, bei denen bspw. die Anzahl der Farben beschränkt ist.

Der Vortragstermin vom 06.07.2011 wurde kurzfristig abgesagt.

Back to the research colloquium site.