Жадный алгоритм в задачах о покрытии/Задачи/vertex-cover — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 3: Строка 3:
 
<m> \ge 2 \cdot OPT</m>
 
<m> \ge 2 \cdot OPT</m>
  
[[Category:Решенные задачи]]
+
[[Category:Нерешенные задачи]]
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->

Версия 07:42, 18 апреля 2013

Для известного 2-приближенного алгоритма для задачи о вершинном покрытии привести пример графа, для которого «этот алгоритм с паросочетаниями» строит покрытие с числом вершин