Approximation unabhängiger Mengen mit der Theta-Funktion
| Talking persons: |
| Dipl.-Inf. Matthias Baumgart |
| Abstract: |
| 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. |
| Times: |
| Wednesday 16th June 2004, 3.30 pm, room 1/B006 |
