Inhalt
zur Navigation
Es gibt keine deutsche Übersetzung dieser Webseite.
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 |