Czy istnieje algorytm do skutecznego utrzymywania informacji o połączeniach dla DAG w przypadku wstawiania / usuwania?

Biorąc pod uwagę ukierunkowany wykres acykliczny, $G(V,E)$ , czy można skutecznie obsługiwać następujące operacje?

• : Określa, czy w G istnieje ścieżkaod węzła a do węzła$isConnected(G,a,b)$$G$$a$$b$
• : Dodaje krawędź od a do b na wykresie$link(G,a,b)$$a$$b$$G$
• : Usuwa krawędź od a do b w$unlink(G,a,b)$$a$$b$$G$
• : Dodaje wierzchołek do G$add(G,a)$
• : Usuwa wierzchołek z G$remove(G,a)$

Kilka uwag:

• Gdybyśmy niedozwolone , wydaje się, że to będzie łatwe do utrzymania informacji więzi, wykorzystując strukturę typu danych rozłącznego-set.$unlink$
• Oczywiście może być realizowane za pomocą głębokości lub przeszukiwanie wszerz, stosując wskaźnik naiwne reprezentacji opartej na wykresie. Ale to jest nieefektywne.$isConnected$

Mam nadzieję na zamortyzowany stały lub logarytmiczny czas dla wszystkich trzech operacji. czy to możliwe?

Opisany przez ciebie problem dotyczy w pełni dynamicznej osiągalności DAG (zwanej również w pełni dynamicznym przechodzeniem przechodzenia na DAG). Nazywa się to w pełni dynamicznym, ponieważ ludzie badają również wersje, w których możliwe są tylko usunięcia (wtedy nazywa się to malejącą osiągalnością) i gdzie możliwe są tylko wstawienia (nazywane przyrostową osiągalnością).

Istnieje kilka kompromisów między czasem aktualizacji a czasem zapytania. Niech będzie liczbą krawędzi, a n liczbą wierzchołków. W przypadku DAG Demetrescu i Italiano (FOCS'00) podali losową strukturę danych, która obsługuje aktualizacje (wstawianie lub usuwanie krawędzi) w czasie O ( n 1,58 ) i zapytania o osiągalność w czasie O ( n 0,58 ) (obsługiwane są również wstawiania / usuwanie węzłów , w czasie O (1)); wynik ten został rozszerzony przez Sankowskiego (FOCS'04) do pracy dla ogólnych grafów kierowanych. Również w przypadku DAG Roditty (SODA'03) wykazał, że można zachować macierz przechodniego zamknięcia w całkowitym czasie O ( m n + I · n 2 + D ), gdzie$m$$n$$n^{1.58}$$n^{0.58}$$mn+I·n^2+D$ to liczba wstawień, D liczba usunięć i oczywiście czas zapytania wynosi O ( 1 ).$I$$D$$1$

W przypadku grafów skierowanych ogólnie znane są następujące czasy (aktualizacja, zapytanie): (O ( ), O (1)) (Demetrescu i Italiano FOCS'00 (amortyzowane), Sankowski FOCS'04 (najgorszy przypadek)), ( O ( m $n^2$ ),O($m\sqrt{n}$ )) (Roditty, Zwick FOCS'02), (O (m+nlogn), O (n)) (Roditty, Zwick STOC'04), (O (n 1,58 ), O (n 0,58 )) i (O (n 1.495 ), O (n 1.495 )) Sankowskiego (FOCS'04).$O(\sqrt{n}$$m+n\log n$$n$$n^{1.58}$$n^{0.58}$$n^{1.495}$$n^{1.495}$

Uzyskiwanie polilogarytmicznego czasu zapytania bez nadmiernego wydłużania czasu aktualizacji jest głównym otwartym problemem, nawet dla DAG.

Myślę, że najlepsze dotychczasowe wyniki zostały omówione w „Zachowując dynamiczne macierze dla w pełni dynamicznego zamknięcia przechodniego” . W artykule omówiono algorytm losowy z czasem zapytania i czasem aktualizacji O ( n 1,58 ) .$O(n^{0.58})$$O(n^{1.58})$

(Dotyczy to tylko pierwszej wersji pytania, z linki unlinkbez addi remove.)