Просмотр кода страницы MAXIMUM INDEPENDENT SET problem

'''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>{\mathcal O}(|V|/(\log |V|)^{2})</math>, and not
approximable within factor <math>|V|^{1-\epsilon}</math> for any <math>\epsilon > 0</math>.