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