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

Заметим, что зависимость границ от параметра <math>\epsilon \;</math> обеспечивает весь диапазон выбора компромиссов между временем запроса и обновления. Для сбалансированного сочетания двух термов в границе обновления теоремы 2 необходимо, чтобы <math>\epsilon \;</math> удовлетворяло равенству <math>\omega(1, \epsilon, 1) = 1 + 2 \epsilon \;</math>. Из наилучшей известной границы на <math>\omega(1, \epsilon, 1) \;</math> [2, 7] следует, что <math>\epsilon < 0,575 \;</math>. Таким образом, наименьшее время обновления составляет <math>O(n^{1,575}) \;</math>, из чего следует время запроса <math>O(n^{0,575}) \;</math>:

Следствие 1 (Деметреску и Итальяно [4, 5], 2000). Пусть дан ориентированный ациклический граф с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий запросы за время O(n0,575), а операции вставки и удаления – за время O(n1,575).

Теорема 3 (Санковски [13], 2004). Пусть дан ориентированный граф общего вида с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время O(n€) для любого O)(l,€,!)-€ + n и операции вставки и удаления – за время O(n £ 2 [0;1], где <w(l,e, 1) – показатель степени при умножении матрицы n x n€ на матрицу n€ x n.