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

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

В основе этих алгоритмов лежит метод поддержки кратчайших путей между всеми парами с операциями вставки и удаления для расстояний, не превышающих d. Для каждой вершины v поддерживаются дерево глубины d кратчайших путей с единственным источником, достигающих v ("Inv"), и дерево вершин, достижимых из v ("Outv"), для любой последовательности операций удаления. Каждая вставка множества вершин, инцидентных v, приводит к перестроению деревьев Inv и Outv. Для каждой пары вершин x, y и каждого значения длины ведется счетчик количества вершин v, таких, что существует путь такой длины от вершины x в Inv к вершине y в Outv.