Große unabhängige Mengen in Graphen mit großer Taillenweite und beschränkter Valenz
| Vortragende(r): |
| Dr. Frank Göring |
| Inhalt: |
| Wir verfeinern einen rundenbasierten Zufallsalgorithmus von Joseph Lauer und Nicholas Wormald zur Erzeugung großer unabhängiger Mengen in gegebenen Graphen so, dass zum einen die Analyse weiterhin durchstehbar ist, zum anderen aber die bisher bekannten untere Schranken für die Unabhängigkeitszahl verbessert werden. Der Schwerpunkt des Vortrages besteht in einer asymptotischen Analyse des vorgestellten Algorithmus. Dies ist eine Gemeinschaftsarbeit mit Jochen Harant und Dieter Rautenbach. |
| Zeiten: |
| Dienstag, der 19.06.2007, 15:30 - 17:30 Uhr, Raum 1/208A |
