4446
правок
Полностью динамический алгоритм транзитивного замыкания: различия между версиями
Материал из WEGA
Полностью динамический алгоритм транзитивного замыкания (посмотреть исходный код)
Версия от 13:13, 10 августа 2014
, 10 августа 2014→Основные результаты
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Инкрементные алгоритмы на диграфах; полностью динамически…») |
Irina (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
== Основные результаты == | == Основные результаты == | ||
В работе [4] предложен полностью динамический детерминистский алгоритм поддержки транзитивного замыкания в ориентированном графе. Для этого алгоритма амортизированное время одного обновления составляет O( | В работе [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. | В основе этих алгоритмов лежит метод поддержки кратчайших путей между всеми парами с операциями вставки и удаления для расстояний, не превышающих d. Для каждой вершины v поддерживаются дерево глубины d кратчайших путей с единственным источником, достигающих v ("Inv"), и дерево вершин, достижимых из v ("Outv"), для любой последовательности операций удаления. Каждая вставка множества вершин, инцидентных v, приводит к перестроению деревьев Inv и Outv. Для каждой пары вершин x, y и каждого значения длины ведется счетчик количества вершин v, таких, что существует путь такой длины от вершины x в Inv к вершине y в Outv. | ||
| Строка 16: | Строка 16: | ||
В работе [6] удалось сократить требуемый объем с O(n3) до O(n2). От множителя log n удалось избавиться [7, 10]. Другие компромиссы между временем обновления и временем запроса приводятся в [1, 7, 8, 9, 10]. Рандомизированный алгоритм транзитивного замыкания, включающий только операции удаления, с общим временем исполнения O(mn), был предложен в [ ]; здесь m – исходное число ребер в графе. Простой алгоритм Монте-Карло для транзитивного замыкания в ациклических графах приведен в [5]. Динамический алгоритм достижимости с единственным источником в диграфе представлен в [8, 9]. Алгоритм поиска кратчайших путей между всеми парами может обеспечить практически такое же время обновления [2]. | В работе [6] удалось сократить требуемый объем с O(n3) до O(n2). От множителя log n удалось избавиться [7, 10]. Другие компромиссы между временем обновления и временем запроса приводятся в [1, 7, 8, 9, 10]. Рандомизированный алгоритм транзитивного замыкания, включающий только операции удаления, с общим временем исполнения O(mn), был предложен в [ ]; здесь m – исходное число ребер в графе. Простой алгоритм Монте-Карло для транзитивного замыкания в ациклических графах приведен в [5]. Динамический алгоритм достижимости с единственным источником в диграфе представлен в [8, 9]. Алгоритм поиска кратчайших путей между всеми парами может обеспечить практически такое же время обновления [2]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
