4446
правок
Точные алгоритмы построения доминирующего множества: различия между версиями
Материал из WEGA
Точные алгоритмы построения доминирующего множества (посмотреть исходный код)
Версия от 13:17, 2 февраля 2014
, 2 февраля 2014→Известные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
== Известные результаты == | == Известные результаты == | ||
Алгоритмическая сложность задачи построения минимального доминирующего множества и ее модификаций при ограничении входных данных графами определенного класса широко изучалась в литературе (см., например, [10]). В частности, известно, что эта задача остается NP-полной на двудольных графах, расщепляемых графах, планарных графах и графах со степенью не выше трех. Существуют алгоритмы с полиномиальным временем исполнения для вычисления минимального доминирующего множества – в частности, для перестановочных, интервальных и k-полигональных графов. Существует также алгоритм с временной сложностью O( | Алгоритмическая сложность задачи построения минимального доминирующего множества и ее модификаций при ограничении входных данных графами определенного класса широко изучалась в литературе (см., например, [10]). В частности, известно, что эта задача остается NP-полной на двудольных графах, расщепляемых графах, планарных графах и графах со степенью не выше трех. Существуют алгоритмы с полиномиальным временем исполнения для вычисления минимального доминирующего множества – в частности, для перестановочных, интервальных и k-полигональных графов. Существует также алгоритм с временной сложностью <math>O(4^k n^{O(1)}) \; </math>, способный построить минимальное доминирующее множество на графах с [[древесная ширина графа|древесной шириной]] не более k. | ||
| Строка 31: | Строка 31: | ||
Тривиальный алгоритм сложности O(2n (n+m)), который просто проверяет все 2n подмножеств вершин на вопрос, не являются ли они доминирующими, очевидным образом решает задачу нахождения доминирующего множества. В 2004 году были разработаны три более быстрых алгоритма. Фомин и коллеги [7] использовали результат из теории графов, установленный Б. Ридом, который показал, что каждый граф с n вершинам с минимальной степенью не менее трех имеет доминирующее множество размера не более 3n/8. Это позволило им разработать алгоритм, решающий задачу нахождения минимального доминирующего множества за время O(20.955n). Алгоритм Рандерата и Ширмейера [11] с временем исполнения O(20.919n) использует любопытные идеи, включающие технику сопоставления, для ограничения пространства поиска. Наконец, Грандони [8] удалось разработать алгоритм нахождения минимального доминирующего множества за время O(20.850n). | Тривиальный алгоритм сложности O(2n (n+m)), который просто проверяет все 2n подмножеств вершин на вопрос, не являются ли они доминирующими, очевидным образом решает задачу нахождения доминирующего множества. В 2004 году были разработаны три более быстрых алгоритма. Фомин и коллеги [7] использовали результат из теории графов, установленный Б. Ридом, который показал, что каждый граф с n вершинам с минимальной степенью не менее трех имеет доминирующее множество размера не более 3n/8. Это позволило им разработать алгоритм, решающий задачу нахождения минимального доминирующего множества за время O(20.955n). Алгоритм Рандерата и Ширмейера [11] с временем исполнения O(20.919n) использует любопытные идеи, включающие технику сопоставления, для ограничения пространства поиска. Наконец, Грандони [8] удалось разработать алгоритм нахождения минимального доминирующего множества за время O(20.850n). | ||
В работе Фомина, Грандони и Кратча [5] представлен простой и удобный для реализации рекурсивный алгоритм ветвления и редукции для решения этой задачи. Он исполняется значительно быстрее предыдущих алгоритмов. В его основе лежит анализ времени исполнения посредством подхода «измеряй и властвуй», представляющего собой метод анализа времени исполнения в наихудшем случае для простых алгоритмов ветвления и редукции, основанный на тщательном отборе меры экземпляра задачи. | В работе Фомина, Грандони и Кратча [5] представлен простой и удобный для реализации рекурсивный алгоритм ветвления и редукции для решения этой задачи. Он исполняется значительно быстрее предыдущих алгоритмов. В его основе лежит анализ времени исполнения посредством подхода «измеряй и властвуй», представляющего собой метод анализа времени исполнения в наихудшем случае для простых алгоритмов ветвления и редукции, основанный на тщательном отборе меры экземпляра задачи. | ||
== Основные результаты == | == Основные результаты == | ||
