4510
правок
Связное доминирующее множество: различия между версиями
Перейти к навигации
Перейти к поиску
м
Связное доминирующее множество (посмотреть исходный код)
Версия от 16:05, 23 января 2013
, 23 января 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 102: | Строка 102: | ||
Суммируя вышеприведенные положения, получаем следующий результат: | Суммируя вышеприведенные положения, получаем следующий результат: | ||
'''Теорема 1.''' Существует <math>(1 + \varepsilon\ )</math>-аппроксимация для построения минимального связного доминирующего множества в связных графах единичных дисков, время исполнения которой составляет <math>n^{O((1/ \varepsilon\ )log(1/ \varepsilon\ )^2)}</math>. | '''Теорема 1.''' Существует <math>(1 + \varepsilon\ )</math>-аппроксимация для построения минимального связного доминирующего множества в связных графах единичных дисков, время исполнения которой составляет <math>n^{O((1/ \varepsilon\ )log(1/ \varepsilon\ )^2)}</math>. | ||