MAXIMUM INDEPENDENT SET problem: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''MAXIMUM INDEPENDENT SET problem''' --- задача о нахождении наибольшего независимого множества. The '''MAXIMUM I…») |
(нет различий)
|
Текущая версия от 13:49, 2 июня 2011
MAXIMUM INDEPENDENT SET problem --- задача о нахождении наибольшего независимого множества.
The MAXIMUM INDEPENDENT SET problem (or MISP) consists in finding an independent set of the largest cardinality. This problem is known to be NP-hard, approximable within factor [math]\displaystyle{ {\mathcal O}(|V|/(\log |V|)^{2}) }[/math], and not approximable within factor [math]\displaystyle{ |V|^{1-\epsilon} }[/math] for any [math]\displaystyle{ \epsilon \gt 0 }[/math].