Полностью динамический алгоритм транзитивного замыкания
Ключевые слова и синонимы
Инкрементные алгоритмы на диграфах; полностью динамический алгоритм поддержки транзитивного замыкания; динамический алгоритм достижимости между всеми парами
Постановка задачи
Разработка структуры данных для ориентированного графа с фиксированным множеством вершин, способной обрабатывать запросы вида «Существует ли путь из i в j?» и поддерживать обновления вида «Вставить ребро {i, j}» и «Удалить ребро {i, j}». Задача состоит в минимизации времени выполнения обновления и запроса для наихудшей последовательности запросов и обновлений. Алгоритмы для решения этой задачи называются «полностью динамическими», поскольку, в отличие от «частично динамических» алгоритмов, выполняют как вставку, так и удаление ребер.
Основные результаты
В работе [4] предложен полностью динамический детерминистский алгоритм поддержки транзитивного замыкания в ориентированном графе. Для этого алгоритма амортизированное время одного обновления составляет O(n2 log n), где n – число вершин графа; время одного запроса в наихудшем случае – O(1). Базовая техника расширяется до приближенных и точных полностью динамических алгоритмов поиска кратчайших путей между всеми парами. В основе этих алгоритмов лежит метод поддержки кратчайших путей между всеми парами с операциями вставки и удаления для расстояний, не превышающих d. Для каждой вершины v поддерживаются дерево глубины d кратчайших путей с единственным источником, достигающих v ("Inv"), и дерево вершин, достижимых из v ("Outv"), для любой последовательности операций удаления. Каждая вставка множества вершин, инцидентных v, приводит к перестроению деревьев Inv и Outv. Для каждой пары вершин x, y и каждого значения длины ведется счетчик количества вершин v, таких, что существует путь такой длины от вершины x в Inv к вершине y в Outv.
Для поддержки транзитивного замыкания для деревьев глубины 2 поддерживаются lg n уровней вышеописанных деревьев, в которых ребра, используемые для построения леса на одном уровне, зависят от путей леса на предыдущем уровне.
В работе [6] удалось сократить требуемый объем с O(n3) до O(n2). От множителя log n удалось избавиться [7, 10]. Другие компромиссы между временем обновления и временем запроса приводятся в [1, 7, 8, 9, 10]. Рандомизированный алгоритм транзитивного замыкания, включающий только операции удаления, с общим временем исполнения O(mn), был предложен в [ ]; здесь 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)
