Точные алгоритмы построения доминирующего множества: различия между версиями

Точные алгоритмы построения доминирующего множества (посмотреть исходный код)

32 байта добавлено , 2 февраля 2014

4446

правок

Версия от 13:56, 2 февраля 2014 (просмотреть исходный код) Irina (обсуждение \| вклад) (→‎Основные результаты) ← Предыдущая правка		Версия от 13:57, 2 февраля 2014 (просмотреть исходный код) Irina (обсуждение \| вклад) (→‎Основные результаты) Следующая правка →
Строка 69:		Строка 69:


	Теорема 5. Существует алгоритм ветвления и редукции в наихудшем случае, способный решить задачу нахождения минимального доминирующего множества (см. теорему 1) за время O(2"/3).		'''Теорема 5. Существует алгоритм ветвления и редукции в наихудшем случае, способный решить задачу нахождения минимального доминирующего множества (см. теорему 1) за время <math>\Omega (2^{n/3}) \; </math>.'''

	== Применение ==		== Применение ==