Аноним

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

Материал из WEGA
м
Строка 31: Строка 31:
Если <math>P \ne NP</math>, то алгоритмов с полиномиальным временем исполнения для построения минимального доминирующего множества не существует. Более того; в [7] было установлено, что за исключением случая <math>SNP \subseteq SUBEXP</math> (крайне маловероятного) не существует алгоритмов нахождения доминирующего множества даже с субэкспоненциальным временем исполнения.
Если <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. Это позволило им разработать алгоритм, решающий задачу нахождения минимального доминирующего множества за время <math>O(2^{0.955n}) \; </math>. Алгоритм Рандерата и Ширмейера [11] с временем исполнения <math>O(2^{0.919n}) \; </math> использует любопытные идеи, включающие технику сопоставления, для ограничения пространства поиска. Наконец, Грандони [8] удалось разработать алгоритм нахождения минимального доминирующего множества за время <math>O(2^{0.850n}) \; </math>.
Тривиальный алгоритм сложности <math>O(2^n (n+m)) \; </math>, который просто проверяет все <math>2^n \; </math> подмножеств вершин на вопрос, не являются ли они доминирующими, очевидным образом решает задачу нахождения доминирующего множества. В 2004 году были разработаны три более быстрых алгоритма. Фомин и коллеги [7] использовали результат из теории графов, установленный Б. Ридом, который показал, что каждый граф с n вершинам с минимальной степенью не менее трех имеет доминирующее множество размера не более <math>3n/8 \; </math>. Это позволило им разработать алгоритм, решающий задачу нахождения минимального доминирующего множества за время <math>O(2^{0.955n}) \; </math>. Алгоритм Рандерата и Ширмейера [11] с временем исполнения <math>O(2^{0.919n}) \; </math> использует любопытные идеи, включающие технику сопоставления, для ограничения пространства поиска. Наконец, Грандони [8] удалось разработать алгоритм нахождения минимального доминирующего множества за время <math>O(2^{0.850n}) \; </math>.


В работе Фомина, Грандони и Кратча [5] представлен простой и удобный для реализации рекурсивный алгоритм ветвления и редукции для решения этой задачи. Он исполняется значительно быстрее предыдущих алгоритмов. В его основе лежит анализ времени исполнения посредством подхода «измеряй и властвуй», представляющего собой метод анализа времени исполнения в наихудшем случае для простых алгоритмов ветвления и редукции, основанный на тщательном отборе меры экземпляра задачи.
В работе Фомина, Грандони и Кратча [5] представлен простой и удобный для реализации рекурсивный алгоритм ветвления и редукции для решения этой задачи. Он исполняется значительно быстрее предыдущих алгоритмов. В его основе лежит анализ времени исполнения посредством подхода «измеряй и властвуй», представляющего собой метод анализа времени исполнения в наихудшем случае для простых алгоритмов ветвления и редукции, основанный на тщательном отборе меры экземпляра задачи.
4551

правка