Jaki jest najszybszy algorytm deterministyczny dla dynamicznej osiągalności digrafu bez usuwania krawędzi?

Jaki jest najlepszy wynik deterministyczny dla utrzymania dynamicznego zamknięcia przechodniego na ukierunkowanym wykresie z tylko wstawieniem krawędzi?

Przeczytałem kilka artykułów na temat problemu dynamicznego zamykania przechodniego zarówno przy wstawianiu, jak i usuwaniu krawędzi. Czy są jednak lepsze algorytmy z tylko wstawianiem krawędzi?

ds.algorithms graph-theory graph-algorithms dynamic-algorithms wei wang
źródło

Czy nie rozwiązuje tego struktura danych znajdowania związków?

Tyson Williams

Czy Twój wykres jest skierowany czy nieukierowany? @TysonWilliams ma rację pod tym względem, że w przypadku nieukierunkowanych wykresów bez usuwania krawędzi, po prostu robisz wyszukiwanie związków (każde wstawienie jest operacją UNION)

Suresh Venkat

Ach .. Zapomniałem wspomnieć, to digraf. Mój zły .... zaktualizuje wtedy.

wei wang

Odpowiedzi:

Stary artykuł Italiano (GF Italiano. Amortyzowana wydajność struktury danych pobierania ścieżki. Theoretical Computer Science, 48 (2–3): 273–281, 1986.) podaje strukturę danych, która obsługuje wstawianie krawędzi w amortyzacji zapytania o czas i osiągalność w stałym czasie. Nie znam lepszych algorytmów przyrostowych. $O(n)$

dziewice
źródło