4551
правка
Деревья Гомори-Ху: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
'''Теорема 1. Пусть G = (V, E) – простой невзвешенный граф, имеющий m ребер и n вершин. Тогда дерево Гомори=Ху для графа G можно построить за ожидаемое время <math>\tilde{O} (mn)</math>''' | '''Теорема 1. Пусть G = (V, E) – простой невзвешенный граф, имеющий m ребер и n вершин. Тогда дерево Гомори=Ху для графа G можно построить за ожидаемое время <math>\tilde{O} (mn)</math>''' | ||
Скорость их алгоритма всегда на коэффициент | Скорость их алгоритма всегда на коэффициент <math>\tilde{\Omega} (n^{2/9}) \; </math> (полилогарифмические сомножители n в <math>\tilde{\Omega}</math>-нотации игнорируются) выше, чем у предыдущей самой быстрой версии алгоритма. | ||