1294
правки
Полностью динамический алгоритм транзитивного замыкания: различия между версиями
Материал из WEGA
Полностью динамический алгоритм транзитивного замыкания (посмотреть исходный код)
Версия от 03:39, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показано 7 промежуточных версий 1 участника) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Инкрементные алгоритмы на диграфах; полностью динамический алгоритм поддержки транзитивного замыкания; динамический алгоритм достижимости между всеми парами | Инкрементные алгоритмы на диграфах; [[полностью динамический алгоритм поддержки транзитивного замыкания]]; [[динамический алгоритм достижимости между всеми парами]] | ||
== Постановка задачи == | == Постановка задачи == | ||
| Строка 8: | Строка 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>. | ||
| Строка 16: | Строка 15: | ||
В работе [6] удалось сократить требуемый объем с <math>O(n^3) \; </math> до <math>O(n^2) \;</math>. От множителя log n удалось избавиться [7, 10]. Другие компромиссы между временем обновления и временем запроса приводятся в [1, 7, 8, 9, 10]. Рандомизированный алгоритм транзитивного замыкания, включающий только операции удаления, с общим временем | В работе [6] удалось сократить требуемый объем с <math>O(n^3) \; </math> до <math>O(n^2) \;</math>. От множителя log n удалось избавиться [7, 10]. Другие компромиссы между временем обновления и временем запроса приводятся в [1, 7, 8, 9, 10]. Рандомизированный алгоритм транзитивного замыкания, включающий только операции удаления, с общим временем выполнения <math>O(mn) \; </math>, был предложен в [8]; здесь m – исходное число ребер в графе. Простой алгоритм Монте-Карло для транзитивного замыкания в ациклических графах приведен в [5]. Динамический алгоритм достижимости с единственным источником в диграфе представлен в [8, 9]. Алгоритм поиска кратчайших путей между всеми парами может обеспечить практически такое же время обновления [2]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Можно ли поддерживать алгоритм достижимости с единственным источником в ориентированном графе с временем o(mn) в наихудшем случае последовательности из m удалений? | Можно ли поддерживать алгоритм достижимости с единственным источником в ориентированном графе с временем o(mn) в наихудшем случае последовательности из m удалений? | ||
Можно ли поддерживать сильно связные компоненты за время o(mn) в наихудшем случае последовательности из m удалений? | Можно ли поддерживать сильно связные компоненты за время o(mn) в наихудшем случае последовательности из m удалений? | ||
== См. также == | == См. также == | ||
* ''[[Алгоритм поиска кратчайших путей в разреженных графах]] | * ''[[Алгоритм поиска кратчайших путей между всеми парами в разреженных графах]] | ||
* ''[[Алгоритм поиска кратчайших путей при помощи матричного произведения]] | * ''[[Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения]] | ||
* ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]] | * ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]] | ||
* ''[[Полностью динамическая связность]] | * ''[[Полностью динамическая связность]] | ||
| Строка 50: | Строка 49: | ||
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) | 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) | ||
[[Категория: Совместное определение связанных терминов]] | |||
