Точные алгоритмы построения доминирующего множества: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 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. Это позволило им разработать алгоритм, решающий задачу нахождения минимального доминирующего множества за время O( | Тривиальный алгоритм сложности <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>. | ||
В работе Фомина, Грандони и Кратча [5] представлен простой и удобный для реализации рекурсивный алгоритм ветвления и редукции для решения этой задачи. Он исполняется значительно быстрее предыдущих алгоритмов. В его основе лежит анализ времени исполнения посредством подхода «измеряй и властвуй», представляющего собой метод анализа времени исполнения в наихудшем случае для простых алгоритмов ветвления и редукции, основанный на тщательном отборе меры экземпляра задачи. | В работе Фомина, Грандони и Кратча [5] представлен простой и удобный для реализации рекурсивный алгоритм ветвления и редукции для решения этой задачи. Он исполняется значительно быстрее предыдущих алгоритмов. В его основе лежит анализ времени исполнения посредством подхода «измеряй и властвуй», представляющего собой метод анализа времени исполнения в наихудшем случае для простых алгоритмов ветвления и редукции, основанный на тщательном отборе меры экземпляра задачи. | ||