4511
правок
Полностью динамическая связность высоких степеней: различия между версиями
Перейти к навигации
Перейти к поиску
Полностью динамическая связность высоких степеней (посмотреть исходный код)
Версия от 22:51, 14 июля 2014
, 14 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 54: | Строка 54: | ||
Теорема 3. Полностью динамическая задача k-реберной связности может быть решена за время: | Теорема 3. Полностью динамическая задача k-реберной связности может быть решена за время: | ||
1. O(log | 1. <math>O(log^4 \; n)</math> на одно обновление и <math>O(log^3 \; n)</math> на один запрос для k = 2 | ||
2. O( | 2. <math>O(n^{2/3}) \; </math> на одно обновление или один запрос для k = 3 | ||
3. O( | 3. <math>O(n \alpha (n)) \; </math> на одно обновление или один запрос для k = 4 | ||
4. O(n log n) на одно обновление | 4. <math>O(n \; log \; n)</math> на одно обновление или один запрос для k > 5. | ||
Теорема 4. Полностью динамическая задача k-вершинной связности может быть решена за время: | Теорема 4. Полностью динамическая задача k-вершинной связности может быть решена за время: | ||
1. O(log | 1. <math>O(log^4 \; n)</math> на одно обновление и <math>O(log^3 \; n)</math> на один запрос для k = 2 | ||
2. O(n) на одно обновление | 2. <math>O(n) \; </math> на одно обновление или один запрос для k = 3 | ||
3. <math>O(n \alpha (n)) \; </math> на одно обновление или один запрос для k = 4. | |||
== Применение == | == Применение == | ||