4430
правок
Компромиссы при решении динамических графовых задач: различия между версиями
Перейти к навигации
Перейти к поиску
Компромиссы при решении динамических графовых задач (посмотреть исходный код)
Версия от 11:52, 19 июня 2018
, 19 июня 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 100: | Строка 100: | ||
Теорема 7 (Родитти и Цвик 2004 [12]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами с единичными весами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время O(t + | '''Теорема 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>''' | ||