Полностью динамическая связность
Ключевые слова и синонимы
Инкрементные алгоритмы на графах; полностью динамический алгоритм поддержки связности графа
Постановка задачи
Разработка структуры данных для неориентированного графа с фиксированным числом вершин, способной обрабатывать запросы вида «Являются ли вершины i и j связанными?» и поддерживать обновления вида «Вставить ребро {i, j}» и «Удалить ребро {i, j}». Задача состоит в минимизации времени выполнения обновления и запроса для наихудшей последовательности запросов и обновлений. Алгоритмы для решения этой задачи называются «полностью динамическими», поскольку, в отличие от «частично динамических" алгоритмов, выполняют как вставку, так и удаление ребер.
Основные результаты
Холм и коллеги [4] предложили первый детерминированный полностью динамический графовый алгоритм, поддерживающий связность неориентированного графа, с полилогарифмическим амортизированным временем на одну операцию – в частности, с амортизированной стоимостью операции обновления O(log2 n) и выполнения запроса O(log n/log log n) в наихудшем случае, где n – количество вершин графа. Базовая техника расширяется для поддержки минимальных остовных деревьев с амортизированной стоимостью одной операции обновления O(log4 n) и 2-реберной связности и двусвязности с амортизированным временем одной операции O(log5 n).
Алгоритм полагается на простую новую технику поддержки остовного леса в графе, обеспечивающую возможность эффективного поиска ребра замены в случае удаления древесного ребра. Эта техника гарантирует, что каждое недревесное ребро проверяется не более log2 n раз. Алгоритм использует уже известные древесные структуры данных – такие как верхушки деревьев или ET-деревья – для хранения и быстрого извлечения информации об остовных деревьях и инцидентных им недревесных дугах.
Алгоритмы с временем запроса O(log n/log log log n) и ожидаемым амортизированным временем обновления O(log n (log log n)3) в случае связности и с ожидаемым амортизированным временем обновления O(log3 n log log n) в случае 2-реберной связности и двусвязности были предложены в [6]. Нижние границы, демонстрирующие континуум компромиссов в случае связности между временем выполнения обновлений и запросов в модели клеточного зонда, согласованные с известными верхними границами, были доказаны в [5]. Более конкретно, если tu и tq – амортизированное время обновления и запроса, соответственно, то tq _ lg(tu /tq) = ˝(lg n) и tu _ lg(tq/tu) = ˝(lg n).
Несколько отличный от них, известный ранее рандомизированный метод вычисления динамической связности с ожидаемым амортизированным временем обновления O(log3 n) был предложен в работе [2] и улучшен до O(log2 n) в [3]. Метод, минимизирующий время обновления в наихудшем случае, а не амортизированное, был предложен в [1]: O(pn) на одно обновление для алгоритма связности, а также для 2-реберной связности и двусвязности.
Открытые вопросы
Можно ли уменьшить время обновления в наихудшем случае до o(n1/2) при полилогарифмическом времени запроса?
Могут ли нижние границы компромиссов, приведенные в работе [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)
