Approximation unabhängiger Mengen mit der Theta-Funktion
| Vortragende(r): |
| Dipl.-Inf. Matthias Baumgart |
| Inhalt: |
| Die Theta-Funktion oder Theta-Zahl eines Graphen sowie deren Eigenschaften werden vorgestellt und untersucht. Im Weiteren wird gezeigt, wie man mit Hilfe der Theta-Zahl eine unabhängige Menge der Größe Ω(m3/(k+1)) findet, wenn der Eingabegraph eine unabhängige Menge der Größe n/k+m (k≥3) enthält. Dieses Ergebnis von Alon und Kahale basiert auf semidefiniter Optimierung sowie einem Färbungsalgorithmus von Karger, Motwani und Sudan. |
| Zeiten: |
| Mittwoch, der 16.06.2004, 15:30 Uhr, Raum 1/B006 |
