4446
правок
Точные алгоритмы построения доминирующего множества: различия между версиями
Материал из WEGA
Точные алгоритмы построения доминирующего множества (посмотреть исходный код)
Версия от 13:57, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 24: | Строка 24: | ||
Задача построения минимального доминирующего множества – одна из основных задач параметризованной сложности [ ]; она является W[2]-полной и, в связи с этим, едва ли окажется разрешимой при помощи алгоритмов с фиксированными параметрами. С другой стороны, на планарных графах она является разрешимой при помощи алгоритмов с фиксированными параметрами. С точки зрения аппроксимации эта задача эквивалентна задаче о минимальном покрытии множества при L-сведении. Существует алгоритм | Задача построения минимального доминирующего множества – одна из основных задач параметризованной сложности [ ]; она является W[2]-полной и, в связи с этим, едва ли окажется разрешимой при помощи алгоритмов с фиксированными параметрами. С другой стороны, на планарных графах она является разрешимой при помощи алгоритмов с фиксированными параметрами. С точки зрения аппроксимации эта задача эквивалентна задаче о минимальном покрытии множества при L-сведении. Существует аппроксимационный алгоритм для нахождения минимального доминирующего множества с коэффициентом <math>1 + ln |V| \; </math>; эта задача не может быть аппроксимирована с коэффициентом <math>(1 - \epsilon ) \; ln |V|</math> для любого <math>\epsilon > 0 \; </math>, за исключением случая <math>NP \subset DTIME(n^{log \; log \; n})</math> [1]. | ||
'''Алгоритмы с умеренно экспоненциальным временем | '''Алгоритмы с умеренно экспоненциальным временем выполнения''' | ||
Если <math>P \ne NP</math>, то алгоритмов с полиномиальным временем исполнения для построения минимального доминирующего множества не существует. Более того; в [7] было установлено, что за исключением случая <math>SNP \subseteq SUBEXP</math> (крайне маловероятного) не существует алгоритмов нахождения доминирующего множества даже с субэкспоненциальным временем исполнения. | Если <math>P \ne NP</math>, то алгоритмов с полиномиальным временем исполнения для построения минимального доминирующего множества не существует. Более того; в [7] было установлено, что за исключением случая <math>SNP \subseteq SUBEXP</math> (крайне маловероятного) не существует алгоритмов нахождения доминирующего множества даже с субэкспоненциальным временем исполнения. | ||
