4551
правка
Точные алгоритмы построения доминирующего множества: различия между версиями
Перейти к навигации
Перейти к поиску
Точные алгоритмы построения доминирующего множества (посмотреть исходный код)
Версия от 13:57, 2 февраля 2014
, 2 февраля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 69: | Строка 69: | ||
Теорема 5. Существует алгоритм ветвления и редукции в наихудшем случае, способный решить задачу нахождения минимального доминирующего множества (см. теорему 1) за время | '''Теорема 5. Существует алгоритм ветвления и редукции в наихудшем случае, способный решить задачу нахождения минимального доминирующего множества (см. теорему 1) за время <math>\Omega (2^{n/3}) \; </math>.''' | ||
== Применение == | == Применение == | ||