Полностью динамический алгоритм достижимости с единственным источником: различия между версиями

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

Простая редукция, предложенная в [1], позволяет сохранять актуальность информации о достижимости из единственного источника, за время ниже квадратичного на одну операцию в ориентированном графе, при выполнении последовательности операций вставки и удаления ребра в различном порядке. Упомянутые границы были впервые приведены для случая ориентированных ациклических графов, однако их можно распространить на ориентированных графов общего вида при помощи следующей теоремы [2]:

В [1] была предложена идея поддержки информации о достижимости из вершины-источника s до всех остальных вершин явным образом при помощи поддержки булева массива R размера n, такого, что R[y] = 1 в том и только том случае, если существует ориентированный путь из s в y. Также поддерживается экземпляр D структуры данных для полностью динамической задачи достижимости из Теоремы 1. После каждой операции вставки или удаления можно обновить структуру D за время <math>O(n^{1,575}) \;</math> и затем перестроить R за время <math>O(n \cdot n^{0,575}) = O(n^{1,575}) \;</math>, положив R[y] <— D.''reachable (s, y)'' для каждой вершины y. Это позволяет получить следующие границы для полностью динамической задачи достижимости с единственным источником.

Задача достижимости в графе особенно актуальна в сфере управления базами данных для поддержки транзитивных запросов на динамических графах отношений [ ]. Она возникает также во множестве других областей – таких как компиляторы, интерактивные системы верификации, сбор мусора и промышленная робототехника.