Жадный алгоритм в задачах о покрытии/Задачи/minimum-hitting-set-k
Материал из DISCOPAL
< Жадный алгоритм в задачах о покрытии | Задачи
Версия от 20:59, 20 сентября 2018; StasFomin (обсуждение | вклад) (Массовая правка: замена :Решенные задачи]] на :Нерешенные задачи]])
Рассмотрим задачу Minimum Hitting Set.
Пусть k — максимальный размер подмножеств из C.
Постройте k-оптимальный полиномиальный алгоритм.
- Hint
- Minimum Hitting Set является обобщением минимального вершинного покрытия.
[ Иерархический вид ]Комментарии
Войдите, чтобы комментировать.