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.

Back to overview.