Approximation von DOMINATING SET und INDEPENDENT DOMINATING SET in erwarteter Polynomialzeit
| Vortragende(r): |
| Dipl.-Inf. Kai Plociennik |
| Inhalt: |
| Die Probleme DOMINATING SET und INDEPENDENT DOMINATING SET lassen sich unter vernünftigen komplexitätstheoretischen Annahmen schwer approximieren, d.h. man kann in Polynomialzeit vermutlich keine gute Gütegarantie erreichen. Es wird gezeigt, wie man bessere Güten garantieren kann, wenn man sich damit zufriedengibt, dass Algorithmen auf zufälligen Eingaben (Graphen) im Erwartungswert polynomielle Laufzeit haben. |
| Zeiten: |
| Mittwoch, der 26.04.2006, 11:30 - 12:30 Uhr, Raum 1/208A |
