Полностью динамическая связность

Ключевые слова и синонимы

Инкрементные алгоритмы на графах; полностью динамический алгоритм поддержки связности графа

Постановка задачи

Разработка структуры данных для неориентированного графа с фиксированным числом вершин, способной обрабатывать запросы вида «Являются ли вершины i и j связанными?» и поддерживать обновления вида «Вставить ребро {i, j}» и «Удалить ребро {i, j}». Задача состоит в минимизации времени выполнения обновления и запроса для наихудшей последовательности запросов и обновлений. Алгоритмы для решения этой задачи называются «полностью динамическими», поскольку, в отличие от «частично динамических» алгоритмов, выполняют как вставку, так и удаление ребер.

Основные результаты

Холм и коллеги [4] предложили первый детерминированный полностью динамический графовый алгоритм, поддерживающий связность неориентированного графа, с полилогарифмическим амортизированным временем на одну операцию – в частности, с амортизированной стоимостью операции обновления [math]\displaystyle{ O(log^2 \; n) }[/math] и выполнения запроса [math]\displaystyle{ O(log \; n / log \; log \; n) }[/math] в наихудшем случае, где n – количество вершин графа. Базовая техника расширяется для поддержки минимальных остовных деревьев с амортизированной стоимостью одной операции обновления [math]\displaystyle{ O(log^4 \; n) }[/math] и 2-реберной связности и двусвязности с амортизированным временем одной операции [math]\displaystyle{ O(log^5 \; n) }[/math].

Алгоритм полагается на простую новую технику поддержки остовного леса в графе, обеспечивающую возможность эффективного поиска ребра замены в случае удаления древесного ребра. Эта техника гарантирует, что каждое недревесное ребро проверяется не более [math]\displaystyle{ log_2 \; n }[/math] раз. Алгоритм использует уже известные древесные структуры данных – такие как верхушки деревьев или ET-деревья – для хранения и быстрого извлечения информации об остовных деревьях и инцидентных им недревесных дугах.

Алгоритмы с временем запроса [math]\displaystyle{ O(log \; n / log \; log\; log \; n) }[/math] и ожидаемым амортизированным временем обновления [math]\displaystyle{ O(log \; n (log \; log \; n)^3) }[/math] в случае связности и с ожидаемым амортизированным временем обновления [math]\displaystyle{ O(log^3 \; n \; log \; log \; n) }[/math] в случае 2-реберной связности и двусвязности были предложены в [6]. Нижние границы, демонстрирующие континуум компромиссов в случае связности между временем выполнения обновлений и запросов в модели клеточного зонда, согласованные с известными верхними границами, были доказаны в [5]. Более конкретно, если [math]\displaystyle{ t_u \; }[/math] и [math]\displaystyle{ t_q \; }[/math] – амортизированное время обновления и запроса, соответственно, то [math]\displaystyle{ t_q \cdot lg(t_u / t_q) = \Omega(lg \; n) }[/math] и [math]\displaystyle{ t_u \cdot lg(t_q / t_u) = \Omega(lg \; n) }[/math].

Несколько отличный от них, известный ранее рандомизированный метод вычисления динамической связности с ожидаемым амортизированным временем обновления [math]\displaystyle{ O(log^3 n) \; }[/math] был предложен в работе [2] и улучшен до [math]\displaystyle{ O(log^2 n) \; }[/math] в [3]. Метод, минимизирующий время обновления в наихудшем случае, а не амортизированное, был предложен в [1]: [math]\displaystyle{ O( \sqrt{n}) }[/math] на одно обновление для алгоритма связности, а также для 2-реберной связности и двусвязности.

Открытые вопросы

Можно ли уменьшить время обновления в наихудшем случае до [math]\displaystyle{ o(n^{1/2}) \; }[/math] при полилогарифмическом времени запроса?

Могут ли нижние границы компромиссов, приведенные в работе [6], быть согласованы для всех возможных вариантов стоимости запросов?

Применение

Алгоритм динамической связности использовался в качестве подпрограммы в нескольких статических графовых алгоритмах – таких как задача нахождения максимального потока в статическом графе [7] – и для ускорения численных экспериментов в модели Поттса.

См. также

• Полностью динамический алгоритм нахождения кратчайших путей между всеми парами
• Полностью динамическое транзитивное замыкание

Литература

1. Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, A.:. Sparsification – a technique for speeding up dynamic graph algorithms. J. ACM 44(5), 669–696.1 (1997)

2. Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4), 502–536 (1999) (presented at ACM STOC 1995)

3. Henzinger, M.R., Thorup, M.: Sampling to provide or to bound: With applications to fully dynamic graph algorithms. Random Struct. Algorithms 11(4), 369–379 (1997) (presented at ICALP 1996)

4. Holm, J., De Lichtenberg, K., Thorup, M.: Poly-logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity. J. ACM 48(4), 723–760 (2001) (presented at ACM STOC 1998)

5. Iyer, R., Karger, D., Rahul, H., Thorup, M.: An experimental study of poly-logarithmic fully-dynamic connectivity algorithms. J. Exp. Algorithmics 6(4) (2001) (presented at ALENEX 2000)

6. P˘atra¸scu, M., Demaine, E.: Logarithmic Lower Bounds in the Cell-ProbeModel. SIAMJ. Comput. 35(4), 932–963 (2006) (presented at ACMSTOC 2004)

7. Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proceedings of the 32th ACM Symposium on Theory of Computing pp. 343–350. ACM STOC (2000)

8. Thorup, M.: Dynamic Graph Algorithms with Applications. In: Halldórsson, M.M. (ed) 7th Scandinavian Workshop on Algorithm Theory (SWAT), Norway, 5–7 July 2000, pp. 1–9

9. Zaroliagis, C.D.: Implementations and experimental studies of dynamic graph algorithms. In: Experimental Algorithmics, Dagstuhl seminar, September 2000, Lecture Notes in Computer Science, vol. 2547. Springer (2002), Journal Article: J. Exp. Algorithmics 229–278 (2000)