4511
правок
Полностью динамические минимальные остовные деревья: различия между версиями
Перейти к навигации
Перейти к поиску
Полностью динамические минимальные остовные деревья (посмотреть исходный код)
Версия от 12:47, 19 июля 2014
, 19 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 41: | Строка 41: | ||
'''Лемма 1. Существует алгоритм поддержки минимального остовного леса, выполняющий только удаление ребер, который может быть инициализирован на графе с n вершинами и m ребрами и который поддерживает любую последовательность удалений ребер за полное время <math>O(m log^2 \; n)</math>. | '''Лемма 1. Существует алгоритм поддержки минимального остовного леса, выполняющий только удаление ребер, который может быть инициализирован на графе с n вершинами и m ребрами и который поддерживает любую последовательность удалений ребер за полное время <math>O(m \; log^2 \; n)</math>. | ||
''' | ''' | ||
| Строка 49: | Строка 49: | ||
'''Лемма 2. Предположим, что существует алгоритм поддержки минимального остовного дерева, выполняющий только удаление ребер, который для любых значений <math>k \; </math> и <math>\ell \;</math> может быть инициализирован на графе с <math>k \; </math> вершинами и <math>\ell \;</math> ребрами и который поддерживает любую последовательность из <math>\Omega ( \ell _ \;</math> удалений за полное время <math>O( \ell \cdot t(k, \ell)) \;</math>, где t – неубывающая функция. Тогда существует полностью динамический алгоритм поддержки минимального остовного дерева для графа с n вершинами, начинающий работу с нулевого числа ребер, который для m ребер поддерживает обновления за время''' | '''Лемма 2. Предположим, что существует алгоритм поддержки минимального остовного дерева, выполняющий только удаление ребер, который для любых значений <math>k \; </math> и <math>\ell \;</math> может быть инициализирован на графе с <math>k \; </math> вершинами и <math>\ell \;</math> ребрами и который поддерживает любую последовательность из <math>\Omega ( \ell _ \;</math> удалений за полное время <math>O( \ell \cdot t(k, \ell)) \;</math>, где t – неубывающая функция. Тогда существует полностью динамический алгоритм поддержки минимального остовного дерева для графа с n вершинами, начинающий работу с нулевого числа ребер, который для m ребер поддерживает обновления за время''' | ||
<math>O \Bigg( log^3 \; n + \sum_{i=1}^{3+log_2 \; m} \sum_{j=1}^i t \; \big( min \{ n, 2^j \}, 2^j \big) \Bigg)</math>. | |||