direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

On s-Zahn Problems

Thomas Köhler (Friedrich-Schiller-Universität Jena)

Das Graphen-Problem Cluster Editing kann über einen verbotenen Teilgraphen beschreiben werden. In diesem Fall ist dieser Teilgraph ein Pfad mit drei Knoten. Wird der mittlere Knoten durch eine Clique der Größe s ersetzt, entsteht eine Graphklasse mit verbotener Teilgraph Charakteristik, die s-Zahn-Graphen. Wir haben die parametrisierte Komplexität zum Finden von solchen Teilgraphen betrachtet. Zudem werden zwei Schranken für die Anzahl an maximalen Cliquen in s-Zahn-Graphen gezeigt. Weiterhin wird ein O Suchbaum für 2-Zahn Deletion und ein paar Datenreduktionsregeln für 2-Zahn Editing und 3-Zahn Deletion vorgestellt.

Zeit
Vortragender
Ort
Sprache
20.04.2011 14:15
Thomas Köhler
FR 6510
deutsch

Back to overview.