Stránka 1 z 1

Aproximovatelnost NM

Napsal: 11. 1. 2012 10:11
od HonzaK
Ahoj,
v poznamkach ze cviceni mam u otazky, zda je mozne aproximacni alg. z prednasky pro vrcholove pokryti (s r=2) pouzit i jako aproximacni
algoritmus pro nezavislou mnozinu (protoze NM = V \ VP). Mam k tomu jen poznamenano, ze "aproximovatlenost je ruzna"...
Nemate k tomu nekdo neco vic?

Diky