Доминирующий набор
-
Определение и свойства доминирующего множества
- Доминирующее множество — это подмножество вершин графа, которое доминирует над всеми остальными вершинами.
- Доминирующее множество является NP-полной задачей, и его размер может быть аппроксимирован с коэффициентом α.
-
История и сложность задачи
- Проблема доминирования активно изучалась с 1950-х годов, и в середине 1970-х годов исследования значительно возросли.
- Ричард Карп доказал NP-полноту задачи о покрытии множества, что имеет прямое отношение к задаче о доминирующем множестве.
-
Алгоритмы и вычислительная сложность
- Существуют L-сокращения между задачами о минимальном доминирующем множестве и о покрытии множества, которые показывают их эквивалентность.
- Аппроксимируемость задачи о покрытии множества хорошо изучена, и существует простой жадный алгоритм для аппроксимации с коэффициентом 1 + log |V|.
- Для особых случаев, таких как единичные дисковые и плоские графы, существуют точные алгоритмы для нахождения доминирующего множества.
-
Параметризованная сложность
- Задача о доминирующем множестве играет ключевую роль в теории параметризованной сложности и является полной для класса W[2].
- Существуют алгоритмы с фиксированными параметрами для задачи о доминирующем множестве на графах без двойников и разреженных графах.
-
Дополнительные понятия и рекомендации
- В статье упоминаются дополнительные понятия, такие как гипотеза Визинга и проблема с установкой покрытия, а также ссылки на литературу для дальнейшего чтения.
Полный текст статьи: