Polynomielle Algorithmen für F-Unabhängigkeit
| Talking persons: |
| Dr. Frank Göring |
| Abstract: |
| 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. |
| Times: |
| Monday 14th January 2008, 4.00 pm - 4.30 pm, room 1/346 |
| literature: |
| Der Vortrag basiert auf der Diplomarbeit von D. Seidewitz. |
