Approximation von Unabhängigkeitszahl und chromatischer Zahl in zufälligen uniformen Hypergraphen
| Talking persons: |
| Dipl.-Inf. Kai Plociennik |
| Abstract: |
| Das Problem, die Unabhängigkeitszahl bzw. die chromatische Zahl eines uniformen Hypergraphen zu berechnen, ist sowohl NP-hart als auch schwer zu approximieren. Im Vortrag wird vorgestellt, wie sich ein Ansatz von Krivelevich und Vu für Graphen auf den Fall d-uniformer Hypergraphen, d ≥ 3 verallgemeinern lässt. Es wird ein Algorithmus vorgestellt, der eine gewisse Approximationsgüte garantiert (die für Algorithmen mit polynomieller worst case Laufzeit nicht erreichbar ist), und der auf zufälligen Hypergraphen, in denen die Kanten unabhängig voneinander gewählt werden, im Durchschnitt eine polynomielle Laufzeit besitzt. |
| Times: |
| Wednesday 28th November 2007, 5.15 pm - 6.45 pm, room 1/208 |
