4551
правка
Точные алгоритмы построения доминирующего множества: различия между версиями
Перейти к навигации
Перейти к поиску
Точные алгоритмы построения доминирующего множества (посмотреть исходный код)
Версия от 13:56, 2 февраля 2014
, 2 февраля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 53: | Строка 53: | ||
Теорема 3. Существует алгоритм ветвления и редукции, способный решить задачу нахождения минимального покрытия множества за время O( | '''Теорема 3. Существует алгоритм ветвления и редукции, способный решить задачу нахождения минимального покрытия множества за время <math>O(2^{0.305(|U| + |S|)}) \; </math> с использованием полиномиального объема памяти.''' | ||
| Строка 59: | Строка 59: | ||
Теорема 4. Существует алгоритм, способный решить задачу нахождения минимального покрытия множества за время O( | '''Теорема 4. Существует алгоритм, способный решить задачу нахождения минимального покрытия множества за время <math>O(2^{0.299(|S| + |U|)}) \; </math> с использованием экспоненциального объема памяти.''' | ||