Освещение проблем
-
Основы задач покрытия
- Задачи покрытия в комбинаторике и информатике касаются вопроса о покрытии одной структуры другой.
- Задачи упаковки являются частными случаями задач покрытия и обычно являются целочисленными линейными программами.
-
Примеры задач покрытия
- Задача о покрытии множества эквивалентна задаче о попадании в множество и имеет частные случаи, такие как задачи о покрытии вершин и ребер.
-
Общая формулировка линейного программирования
- Линейная программа минимизации может рассматриваться как задача покрытия, если все коэффициенты в матрице неотрицательны.
- Оптимальное решение целочисленной линейной программы — это покрытие с минимальными затратами.
-
Виды проблем с покрытием
- В теории графов, вычислительной геометрии и других областях существуют различные типы задач покрытия.
- Существуют стохастические версии задач покрытия.
-
Покрытие сетками Петри
- В сетях Петри задача покрытия заключается в поиске отрезка сети, который покрывает заданную разметку.
-
Радужное покрытие
- В задаче радужного покрытия требуется, чтобы покрытие содержало ровно один объект каждого цвета.
- Задача радужного покрытия является NP-сложной.
-
Бесконфликтное покрытие
- Бесконфликтное покрытие — это подмножество объектов, которое является независимым множеством в графе конфликтов.
- Задача о бесконфликтном покрытии множества является FPT-сложной, если задача о геометрическом покрытии разрешима с фиксированным параметром.
Полный текст статьи: