Аноним

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

Материал из WEGA
Строка 100: Строка 100:




Теорема 7 (Родитти и Цвик 2004 [12]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами с единичными весами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время O(t + " °g") в наихудшем случае, а операции вставки и удаления – за время
'''Теорема 7 (Родитти и Цвик 2004 [12]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами с единичными весами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время <math>O(t + \frac{n \; log \; n}{k})</math> в наихудшем случае, а операции вставки и удаления – за амортизированное время <math>O(\frac{m \; n^2 log \; n}{t^2} + km + \frac{m \; n \; log \; n}{k})</math>'''




4551

правка