MINIMUM VERTEX COVER problem

Материал из WEGA
Версия от 14:43, 2 июня 2011; Glk (обсуждение | вклад) (Новая страница: «'''MINIMUM VERTEX COVER problem''' --- задача о наименьшем вершинном покрытии. The '''MINIMUM VERTEX COVER problem''' (or ''' MVC…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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.