4551
правка
Точные алгоритмы построения доминирующего множества: различия между версиями
Перейти к навигации
Перейти к поиску
Точные алгоритмы построения доминирующего множества (посмотреть исходный код)
Версия от 00:28, 2 февраля 2014
, 2 февраля 2014→Постановка задачи
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача построения доминирующего множества представляет собой классическую [[NP- | Задача построения доминирующего множества представляет собой классическую [[NP-Полная_задача|NP-полную задачу]] оптимизации, входящую в более широкий класс задач о покрытии. Сотни статей были посвящены этой задаче, которая имеет огромное значение для определения местоположения. | ||
| Строка 16: | Строка 16: | ||
Дано: простой неориентированный граф G = (V, E). Требуется: найти минимальное доминирующее множество D графа G. | Дано: простой неориентированный граф G = (V, E). Требуется: найти минимальное доминирующее множество D графа G. | ||
Представляют интерес различные модификации задачи построения доминирующего множества; некоторые из них были получены посредством накладывания дополнительных ограничений на доминирующее множество – к примеру, оно может быть независимым или связным. В теории графов проблеме доминирования и множеству ее модификаций посвящен обширный список работ (см., например, [9]). В контексте графовых алгоритмов задача построения минимального доминирующего множества и некоторых его модификаций (таких как независимое доминирующее множество или связное доминирующее множество) рассматривается как типовая для решения NP-полных задач с использованием различных алгоритмических подходов. | Представляют интерес различные модификации задачи построения доминирующего множества; некоторые из них были получены посредством накладывания дополнительных ограничений на доминирующее множество – к примеру, оно может быть независимым или связным. В теории графов проблеме доминирования и множеству ее модификаций посвящен обширный список работ (см., например, [9]). В контексте графовых алгоритмов задача построения минимального доминирующего множества и некоторых его модификаций (таких как независимое доминирующее множество или связное доминирующее множество) рассматривается как типовая для решения NP-полных задач с использованием различных алгоритмических подходов. | ||
== Известные результаты == | == Известные результаты == | ||