4551
правка
Компромиссы при решении динамических графовых задач: различия между версиями
Перейти к навигации
Перейти к поиску
м
Компромиссы при решении динамических графовых задач (посмотреть исходный код)
Версия от 12:23, 19 июня 2018
, 19 июня 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 89: | Строка 89: | ||
'''Теорема 6 (Родитти и Цвик 2004 [11]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время O(m+ n log n), а запросы – за время O(n) в наихудшем случае.''' | '''Теорема 6 (Родитти и Цвик 2004 [11]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время O(m + n log n), а запросы – за время O(n) в наихудшем случае.''' | ||
| Строка 97: | Строка 97: | ||
'''Динамический алгоритм нахождения кратчайших путей''' | '''Динамический алгоритм нахождения кратчайших путей''' | ||
Первый эффективный компромиссный алгоритм для динамического поиска кратчайших путей предложили Родитти и Цвик для специального случая разреженных графов с единичными весами ребер [12]: | |||
| Строка 103: | Строка 103: | ||
Положив <math>k = (n \; log \; n)^{1/2}</math> и <math>(n \; log \; n)^{1/2} \le t \le n^{3/4} \; (log \; n)^{1/4}</math> в теореме 7, можно получить амортизированное время обновления <math>O(\frac{m \; n^2 \; log \; n}{t^2})</math> и время выполнения запросов в наихудшем случае <math>O(t) \;</math>. Самое быстрое время обновления, <math>O(m \sqrt{n \; log n})</math>, можно получить, если выбрать <math>t = n^{3/4}(log \; n)^{1/4}</math>. | Положив <math>k = (n \; log \; n)^{1/2}</math> и <math>(n \; log \; n)^{1/2} \le t \le n^{3/4} \; (log \; n)^{1/4}</math> в теореме 7, можно получить амортизированное время обновления <math>O(\frac{m \; n^2 \; log \; n}{t^2})</math> и время выполнения запросов в наихудшем случае <math>O(t) \;</math>. Самое быстрое время обновления, <math>O(m \sqrt{n \; log \; n})</math>, можно получить, если выбрать <math>t = n^{3/4}(log \; n)^{1/4}</math>. | ||