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

Санковски также показал, как получить еще более быстрое время обновления O(n1.495) за счет увеличения времени выполнения запросов <math>O(n^{1,495}) \;</math>:

Теорема 4 (Санковски [13], 2004). Пусть дан ориентированный граф общего вида с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий запросы и операции вставки и удаления за время O(n1,495).

Теорема 5 (Родитти и Цвик 2002 [10]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время O(mpn), а запросы – за время O(pn) в наихудшем случае.

Теорема 6 (Родитти и Цвик 2004 [11]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время O(m+ n log n), а запросы – за время O(n) в наихудшем случае.

Заметим, что результаты теорем 5 и 6 являются субквадратичными для m = o(n1,5) и m = o(n2), соответственно. Более того, они не основываются на быстром перемножении матриц, которое является теоретически эффективным, но непрактичным.