MINIMUM VERTEX COVER problem: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''MINIMUM VERTEX COVER problem''' --- задача о наименьшем вершинном покрытии. The '''MINIMUM VERTEX COVER problem''' (or ''' MVC…») |
(нет различий)
|
Текущая версия от 07:43, 2 июня 2011
MINIMUM VERTEX COVER problem --- задача о наименьшем вершинном покрытии.
The MINIMUM VERTEX COVER problem (or MVCP) consists in finding a cover of the smallest cardinality. This problem is known to be NP-hard, approximable within factor 2 and not approximable within factor 1.1666.