Approximation von DOMINATING SET und INDEPENDENT DOMINATING SET in erwarteter Polynomialzeit
| Talking persons: |
| Dipl.-Inf. Kai Plociennik |
| Abstract: |
| 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. |
| Times: |
| Wednesday 26th April 2006, 11.30 am - 12.30 pm, room 1/208A |
