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

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

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

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

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

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

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

В основе этих алгоритмов лежит метод поддержки кратчайших путей между всеми парами с операциями вставки и удаления для расстояний, не превышающих d. Для каждой вершины v поддерживаются дерево глубины d кратчайших путей с единственным источником, достигающих v - [math]\displaystyle{ In_v \; }[/math] - и дерево вершин, достижимых из v - [math]\displaystyle{ Out_v \; }[/math], для любой последовательности операций удаления. Каждая вставка множества вершин, инцидентных v, приводит к перестроению деревьев [math]\displaystyle{ In_v \; }[/math] и [math]\displaystyle{ Out_v \; }[/math]. Для каждой пары вершин x, y и каждого значения длины ведется счетчик количества вершин v, таких, что существует путь такой длины от вершины x в [math]\displaystyle{ In_v \; }[/math] к вершине y в [math]\displaystyle{ Out_v \; }[/math].

Для поддержки транзитивного замыкания для деревьев глубины 2 поддерживаются lg n уровней вышеописанных деревьев, в которых ребра, используемые для построения леса на одном уровне, зависят от путей леса на предыдущем уровне.

В работе [6] удалось сократить требуемый объем с [math]\displaystyle{ O(n^3) \; }[/math] до [math]\displaystyle{ O(n^2) \; }[/math]. От множителя log n удалось избавиться [7, 10]. Другие компромиссы между временем обновления и временем запроса приводятся в [1, 7, 8, 9, 10]. Рандомизированный алгоритм транзитивного замыкания, включающий только операции удаления, с общим временем выполнения [math]\displaystyle{ O(mn) \; }[/math], был предложен в [8]; здесь m – исходное число ребер в графе. Простой алгоритм Монте-Карло для транзитивного замыкания в ациклических графах приведен в [5]. Динамический алгоритм достижимости с единственным источником в диграфе представлен в [8, 9]. Алгоритм поиска кратчайших путей между всеми парами может обеспечить практически такое же время обновления [2].

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

Можно ли поддерживать алгоритм достижимости с единственным источником в ориентированном графе с временем o(mn) в наихудшем случае последовательности из m удалений?

Можно ли поддерживать сильно связные компоненты за время o(mn) в наихудшем случае последовательности из m удалений?

См. также

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

Литература

1. Demestrescu, C., Italiano, G.F.: Trade-offs for fully dynamic transitive closure on DAG's: breaking through the O(n2) barrier, (presented in FOCS 2000). J. ACM 52(2), 147-156 (2005)

2. Demestrescu, C., Italiano, G.F.: A new approach to dynamic all-pairs shortest paths, (presented in STOC 2003). J. ACM 51(6), 968-992 (2004)

3. Frigioni, D., Miller, T., Nanni, U., Zaroliagis, C.D.: An experimental study of dynamic algorithms for transitive closure. ACM J Exp. Algorithms 6(9) (2001)

4. King, V.: Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proceedings of the 40th Annual IEEE Symposium on Foundation of Computer Science. ComiIEEE FOCS pp. 81-91. IEEE Computer Society, New York (1999)

5. King, V., Sagert, G.: A fully dynamic algorithm for maintaining the transitive closure, (presented in FOCS 1999). JCCS 65(1), 150-167(2002)

6. King, V., Thorup, M.: A space saving trick for dynamic transitive closure and shortest path algorithms. In: Proceedings of the 7th Annual International Conference of Computing and Com-inatorics, vol. 2108/2001, pp. 269-277. Lect. Notes Comp. Sci. COCOON Springer, Heidelberg (2001)

7. Roditty, L.: A faster and simpler fully dynamic transitive closure. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM IEEE SODA, pp. 404^12. ACM, Baltimore (2003)

8. Roditty, L., Zwick, U.: Improved dynamic reachability algorithms for directed graphs. In: Proceedings of the 43rd Annual Symposium on Foundation of Computer Science. IEEE FOCS, pp. 679-688 IEEE Computer Society, Vancouver, Canada (2002)

9. Roditty, L., Zwick, U.: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: Proceedings of the 36th ACM Symposium on Theory of Computing. ACM STOC, pp. 184-191 ACM, Chicago (2004)

10. Sankowski, S.: Dynamic transitive closure via dynamic matrix inverse. In: Proceedings of the 45th Annual Symposium on Foundations of Computer Science. IEEE FOCS, 509-517, IEEE Computer Society, Rome, Italy (2004)