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

'''Алгоритмы с умеренно экспоненциальным временем исполнения'''

 

Если <math>P \ne NP</math>, то алгоритмов с полиномиальным временем исполнения для построения минимального доминирующего множества не существует. Более того; в [7] было установлено, что за исключением случая <math>SNP \subseteq SUBEXP</math> (крайне маловероятного) не существует алгоритмов нахождения доминирующего множества даже с субэкспоненциальным временем исполнения.

 

Тривиальный алгоритм сложности <math>O(2^n (n+m)) \; </math>, который просто проверяет все <math>2^n \; </math> подмножеств вершин на вопрос, не являются ли они доминирующими, очевидным образом решает задачу нахождения доминирующего множества. В 2004 году были разработаны три более быстрых алгоритма. Фомин и коллеги [7] использовали результат из теории графов, установленный Б. Ридом, который показал, что каждый граф с n вершинам с минимальной степенью не менее трех имеет доминирующее множество размера не более 3n/8. Это позволило им разработать алгоритм, решающий задачу нахождения минимального доминирующего множества за время O(20.955n). Алгоритм Рандерата и Ширмейера [11] с временем исполнения O(20.919n) использует любопытные идеи, включающие технику сопоставления, для ограничения пространства поиска. Наконец, Грандони [8] удалось разработать алгоритм нахождения минимального доминирующего множества за время O(20.850n).