4551
правка
Компромиссы при решении динамических графовых задач: различия между версиями
Перейти к навигации
Перейти к поиску
м
Компромиссы при решении динамических графовых задач (посмотреть исходный код)
Версия от 12:13, 19 июня 2018
, 19 июня 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 109: | Строка 109: | ||
Теорема 8 (Санковски [14], 2005). Пусть дан ориентированный граф общего вида с n вершинами и единичными весами ребер. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время <math>O(n^{1,288}) \;</math>, а операции вставки и удаления – за время <math>O(n^{1,932}) \;</math>. | '''Теорема 8 (Санковски [14], 2005). Пусть дан ориентированный граф общего вида с n вершинами и единичными весами ребер. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время <math>O(n^{1,288}) \;</math>, а операции вставки и удаления – за время <math>O(n^{1,932}) \;</math>.''' | ||
| Строка 117: | Строка 117: | ||
! Тип алгоритма | ! Тип алгоритма | ||
! Время обновления | ! Время обновления | ||
! Время | ! Время запроса | ||
! Источник | ! Источник | ||
|- | |- | ||
| Строка 123: | Строка 123: | ||
| Монте-Карло | | Монте-Карло | ||
| <math>O(m \sqrt{n} \; log^2 n)</math> аморт. | | <math>O(m \sqrt{n} \; log^2 n)</math> аморт. | ||
| O(n /log n) | | <math>O(n / log \; n)</math> | ||
| Хензингер | | Хензингер, Кинг [6] | ||
|- | |- | ||
| Ориентированный ациклический граф | |width="140pt"| Ориентированный ациклический граф | ||
| Монте-Карло | | Монте-Карло | ||
| <math>O(n^{1,575}) \;</math> | | <math>O(n^{1,575}) \;</math> | ||