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

Теорема 1. Пусть дан ориентированный граф общего вида с n вершинами. Существует структура данных для решения полностью динамической задачи достижимости, поддерживающая операции вставки и удаления за время O(n1,575), а запросы о достижимости – за время O(n0.575). Алгоритм является рандомизированным с односторонней ошибкой.

В [ ] была предложена идея поддержки информации о достижимости из вершины-источника s до всех остальных вершин явным образом при помощи поддержки булева массива R размера n, такого, что R[y] = 1 в том и только том случае, если существует ориентированный путь из s в y. Также поддерживается экземпляр D структуры данных для полностью динамической задачи достижимости из Теоремы 1. После каждой операции вставки или удаления можно обновить структуру D за время O(n1,575) и затем перестроить R за время O(n • n0,575) = O(n1,575), положив R[y] <— D:reachable (s, y) для каждой вершины y. Это позволяет получить следующие границы для полностью динамической задачи достижимости с единственным источником.

Теорема 2. Пусть дан ориентированный граф общего вида с n вершинами. Существует структура данных для решения полностью динамической задачи достижимости с единственным источником, поддерживающая операции вставки и удаления за время O(n1,575), а запросы о достижимости – за время O(1).