Polynomielle Algorithmen für F-Unabhängigkeit
| Vortragende(r): |
| Dr. Frank Göring |
| Inhalt: |
| Dieser Vortrag ist Teil des Workshops "Algorithmen und Graphen". Sei F ein Graph. Eine Knotenmenge S ist F-unabhängig in einem Graphen G, wenn der durch S induzierte Untergraph G[S] keine Kopie von F als Untergraph enthält. Harant, Schiermeyer, Rautenbach, und G. zeigten, dass das Problem zu entscheiden, ob G eine F-unabhängige Menge der Kardinalität k enthält, NP-schwer ist. Im Vortrag diskutieren wir zwei Graphenklassen, für die es möglich ist eine F-unabhängige Menge mit maximaler Kardinalität in Linearzeit zu finden: Die Klasse von Graphen mit beschränkter Baumweite und die Klasse der gut-F-überdeckten Graphen. Hierbei heißt ein Graph gut-F-überdeckt, wenn die Familie der F-unabhängigen Teilmengen der Knotenmenge ein Matroid formt. Offene Fragen bzgl. der Klasse der gut-F-überdeckten Graphen werden vorgestellt. |
| Zeiten: |
| Montag, der 14.01.2008, 16:00 - 16:30 Uhr, Raum 1/346 |
| Literatur: |
| Der Vortrag basiert auf der Diplomarbeit von D. Seidewitz. |
