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.

Источник — http://pco.iis.nsk.su/wega/index.php?title=MINIMUM_VERTEX_COVER_problem&oldid=8095