4430
правок
Полностью динамический алгоритм достижимости с единственным источником: различия между версиями
Перейти к навигации
Перейти к поиску
м
Полностью динамический алгоритм достижимости с единственным источником (посмотреть исходный код)
Версия от 10:40, 20 февраля 2018
, 20 февраля 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 38: | Строка 38: | ||
Первым улучшением по сравнению с двумя базовыми решениями стал алгоритм Деметреску и Итальяно, которые показали, как поддерживать операции обновления за время O(n^{1,575}), а запросы о достижимости – за время O(1) [1] в ориентированном ациклическом графе. Их результат основывается на простой редукции решения для задачи с единственным источником до задачи для всех пар. Используя результат Санковски [2], можно расширить вышеприведенные границы для общего случая ориентированных графов. | Первым улучшением по сравнению с двумя базовыми решениями стал алгоритм Деметреску и Итальяно, которые показали, как поддерживать операции обновления за время <math>O(n^{1,575}) \;</math>, а запросы о достижимости – за время O(1) [1] в ориентированном ациклическом графе. Их результат основывается на простой редукции решения для задачи с единственным источником до [[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами|задачи для всех]] пар. Используя результат Санковски [2], можно расширить вышеприведенные границы для общего случая ориентированных графов. | ||
== Основные результаты == | == Основные результаты == | ||