Компромиссы при решении динамических графовых задач: различия между версиями

Положив <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>.

Теорема 8 (Санковски [14], 2005). Пусть дан ориентированный граф общего вида с n вершинами и единичными весами ребер. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время <math>O(n^{1,288}) \;</math>, а операции вставки и удаления – за время <math>O(n^{1,932}) \;</math>.

! Тип графа

! Тип алгоритма

! Время обновления

! Время выполнения запроса

! Источник