4446
правок
Компромиссы при решении динамических графовых задач: различия между версиями
Материал из WEGA
Компромиссы при решении динамических графовых задач (посмотреть исходный код)
Версия от 12:04, 19 июня 2018
, 19 июня 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 112: | Строка 112: | ||
{| class="wikitable" | {| class="wikitable" style="text-align:center" | ||
|- | |- | ||
! Тип графа | ! Тип графа | ||
| Строка 120: | Строка 120: | ||
! Источник | ! Источник | ||
|- | |- | ||
| | | Граф общего вида | ||
| | | Монте-Карло | ||
| | | <math>O(m \sqrt{n} \; log^2 n)</math> аморт. | ||
| | | O(n /log n) | ||
| | | Хензингер и Кинг [6] | ||
|- | |- | ||
| | | Ориентированный ациклический граф | ||
| | | Монте-Карло | ||
| | | <math>O(n^{1,575}) \;</math> | ||
| | | <math>O(n^{0,575}) \;</math> | ||
| | | | ||
|- | |- | ||
| | | Граф общего вида | ||
| | | Монте-Карло | ||
| | | <math>O(n^{1,575}) \;</math> | ||
| | | | ||
| | | | ||
|- | |- | ||
| | | Граф общего вида | ||
| | | Монте-Карло | ||
| | | <math>O(n^{0,575}) \;</math> | ||
| | | | ||
| | | | ||
|- | |- | ||
| | | Граф общего вида | ||
| | | Детерминированный | ||
| | | <math>O(n^{1,495}) \;</math> | ||
| | | <math>O(n^{1,495}) \;</math> | ||
| | | | ||
|- | |- | ||
| | | Граф общего вида | ||
| | | Детерминированный | ||
| | | | ||
| | | | ||
| Строка 157: | Строка 157: | ||
|} | |} | ||
O(n0,575) Деметреску, Итальяно [4] | |||
O(n1,575) O(n0,575) Санковски [13] | |||
O(n1,495) O(n1,495) Санковски [13] | |||
O(mn) аморт. O(pn) Родитти, Цвик [10] | |||
O(m + n log n) аморт. O(n) Родитти, Цвик [11] | |||
Таблица 1. Полностью динамический алгоритм транзитивного замыкания с неявным представлением решения | Таблица 1. Полностью динамический алгоритм транзитивного замыкания с неявным представлением решения | ||
