Точные алгоритмы построения доминирующего множества: различия между версиями

Задача построения доминирующего множества представляет собой классическую [[NP-Полная_задача|NP-полную задачу]] оптимизации, входящую в более широкий класс задач о покрытии. Сотни статей были посвящены этой задаче, которая имеет огромное значение для определения местоположения.

Определение 1. Пусть задан простой неориентированный граф G = (V, E). Подмножество вершин D in V называется доминирующим множеством, если каждая вершина u 2 V — D имеет соседа в D. Задача построения минимального доминирующего множества (minimum dominating set, MDS) заключается в поиске минимального доминирующего множества графа G, т.е. доминирующего множества G с минимальной мощностью.