4551
правка
Точные алгоритмы построения доминирующего множества: различия между версиями
Перейти к навигации
Перейти к поиску
Точные алгоритмы построения доминирующего множества (посмотреть исходный код)
Версия от 13:44, 2 февраля 2014
, 2 февраля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 37: | Строка 37: | ||
== Основные результаты == | == Основные результаты == | ||
Теорема 1. Существует алгоритм ветвления и редукции, способный решить задачу нахождения минимального доминирующего множества за время O( | '''Теорема 1. Существует алгоритм ветвления и редукции, способный решить задачу нахождения минимального доминирующего множества за время <math>O(2^{0:610n}) \; </math> с использованием полиномиального объема памяти. | ||
''' | |||
'''Теорема 2. Существует алгоритм, способный решить задачу нахождения минимального доминирующего множества за время <math>O(2^{0:598n}) \; </math> с использованием экспоненциального объема памяти.''' | |||
Алгоритмы из теорем 1 и 2 представляют собой простые последовательности преобразований минимального доминирующего множества в [[минимальное покрытие множества]] (minimum set cover, MSC) в сочетании с новыми алгоритмами вычисления минимального покрытия множества, время исполнения которых является умеренно экспоненциальным. | |||
Алгоритмы из теорем 1 и 2 представляют собой простые последовательности преобразований минимального доминирующего множества в минимальное покрытие множества (minimum set cover, MSC) в сочетании с новыми алгоритмами вычисления минимального покрытия множества, время исполнения которых является умеренно экспоненциальным. | |||
| Строка 69: | Строка 69: | ||
Теорема 5. Существует алгоритм ветвления и редукции в наихудшем случае, способный решить задачу нахождения минимального доминирующего множества (см. теорему 1) за время O(2"/3). | Теорема 5. Существует алгоритм ветвления и редукции в наихудшем случае, способный решить задачу нахождения минимального доминирующего множества (см. теорему 1) за время O(2"/3). | ||
== Применение == | == Применение == | ||