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

Холм и коллеги [4] предложили первый детерминированный полностью динамический графовый алгоритм, поддерживающий связность неориентированного графа, с полилогарифмическим амортизированным временем на одну операцию – в частности, с амортизированной стоимостью операции обновления O(log2 n) и выполнения запроса O(log n/log log n) в наихудшем случае, где n – количество вершин графа. Базовая техника расширяется для поддержки минимальных остовных деревьев с амортизированной стоимостью одной операции обновления O(log4 n) и 2-реберной связности и двусвязности с амортизированным временем одной операции O(log5 n).

Алгоритм полагается на простую новую технику поддержки остовного леса в графе, обеспечивающую возможность эффективного поиска ребра замены в случае удаления древесного ребра. Эта техника гарантирует, что каждое недревесное ребро проверяется не более log2 n раз. Алгоритм использует уже известные древесные структуры данных – такие как верхушки деревьев или ET-деревья – для хранения и быстрого извлечения информации об остовных деревьях и инцидентных им недревесных дугах.

Алгоритмы с временем запроса O(log n/log log log n) и ожидаемым амортизированным временем обновления O(log n (log log n)3) в случае связности и с ожидаемым амортизированным временем обновления O(log3 n log log n) в случае 2-реберной связности и двусвязности были предложены в [6]. Нижние границы, демонстрирующие континуум компромиссов в случае связности между временем выполнения обновлений и запросов в модели клеточного зонда, согласованные с известными верхними границами, были доказаны в [5]. Более конкретно, если tu и tq – амортизированное время обновления и запроса, соответственно, то tq _ lg(tu /tq) = ˝(lg n) и tu _ lg(tq/tu) = ˝(lg n).