4446
правок
Полностью динамический алгоритм транзитивного замыкания: различия между версиями
Материал из WEGA
Полностью динамический алгоритм транзитивного замыкания (посмотреть исходный код)
Версия от 13:17, 10 августа 2014
, 10 августа 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 7: | Строка 7: | ||
== Основные результаты == | == Основные результаты == | ||
В работе [4] предложен полностью динамический детерминистский алгоритм поддержки транзитивного замыкания в ориентированном графе. Для этого алгоритма амортизированное время одного обновления составляет <math>O(n^2 \; log \; n)</math>, где n – число вершин графа; время одного запроса в наихудшем случае – <math>O(1) \; </math>. Базовая техника расширяется до приближенных и точных полностью динамических алгоритмов поиска кратчайших путей между всеми парами. | В работе [4] предложен первый полностью динамический детерминистский алгоритм поддержки транзитивного замыкания в ориентированном графе. Для этого алгоритма амортизированное время одного обновления составляет <math>O(n^2 \; log \; n)</math>, где n – число вершин графа; время одного запроса в наихудшем случае – <math>O(1) \; </math>. Базовая техника расширяется до приближенных и точных полностью динамических алгоритмов поиска кратчайших путей между всеми парами. | ||
В основе этих алгоритмов лежит метод поддержки кратчайших путей между всеми парами с операциями вставки и удаления для расстояний, не превышающих d. Для каждой вершины v поддерживаются дерево глубины d кратчайших путей с единственным источником, достигающих v - <math>In_v \;</math> - и дерево вершин, достижимых из v - <math>Out_v \;</math>, для любой последовательности операций удаления. Каждая вставка множества вершин, инцидентных v, приводит к перестроению деревьев <math>In_v \;</math> и <math>Out_v \;</math>. Для каждой пары вершин x, y и каждого значения длины ведется счетчик количества вершин v, таких, что существует путь такой длины от вершины x в <math>In_v \;</math> к вершине y в <math>Out_v \;</math>. | В основе этих алгоритмов лежит метод поддержки кратчайших путей между всеми парами с операциями вставки и удаления для расстояний, не превышающих d. Для каждой вершины v поддерживаются дерево глубины d кратчайших путей с единственным источником, достигающих v - <math>In_v \;</math> - и дерево вершин, достижимых из v - <math>Out_v \;</math>, для любой последовательности операций удаления. Каждая вставка множества вершин, инцидентных v, приводит к перестроению деревьев <math>In_v \;</math> и <math>Out_v \;</math>. Для каждой пары вершин x, y и каждого значения длины ведется счетчик количества вершин v, таких, что существует путь такой длины от вершины x в <math>In_v \;</math> к вершине y в <math>Out_v \;</math>. | ||
