MINIMUM VERTEX COVER problem

Материал из WEGA
Перейти к навигации Перейти к поиску

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.