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

'''Следствие 1 (Санковски [13], 2004). Пусть дан ориентированный граф общего вида с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий запросы за время <math>O(n^{0,575}) \;</math>:, а операции вставки и удаления – за время <math>O(n^{1,575}) \;</math>.'''