Жадный алгоритм в задачах о покрытии/Задачи/minimum-hitting-set-k — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «Рассмотрим задачу Minimum Hitting Set. Пусть ''k'' — максимальный размер подмножеств из ''C''. Пос…») |
(нет различий)
|
Версия 13:06, 9 декабря 2017
Рассмотрим задачу Minimum Hitting Set.
Пусть k — максимальный размер подмножеств из C.
Постройте k-оптимальный полиномиальный алгоритм.
- Hint
- Minimum Hitting Set является обобщением минимального вершинного покрытия.