Biorąc pod uwagę ukierunkowany wykres acykliczny, , 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 b
- : Dodaje krawędź od a do b na wykresie G
- : Usuwa krawędź od a do b w G
- : Dodaje wierzchołek do G
- : Usuwa wierzchołek z G
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.
- 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.
Mam nadzieję na zamortyzowany stały lub logarytmiczny czas dla wszystkich trzech operacji. czy to możliwe?
ds.algorithms
graph-algorithms
directed-acyclic-graph
online-algorithms
Justin Kilpatrick
źródło
źródło
remove
usuwa również krawędzie zdarzeń? Jeśli tak, wymaganie od tej operacji czasu O (log n) może być zbyt duże, aby mieć nadzieję….Odpowiedzi:
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 ), gdziem n n1.58 n0.58 mn+I⋅n2+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 √n2 ),O( √mn−−√ )) (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(n−−√ m+nlogn n n1.58 n0.58 n1.495 n1.495
Uzyskiwanie polilogarytmicznego czasu zapytania bez nadmiernego wydłużania czasu aktualizacji jest głównym otwartym problemem, nawet dla DAG.
źródło
(O(1),O(n^2))
lub(O(m),O(n+m))
.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(n0.58) O(n1.58)
(Dotyczy to tylko pierwszej wersji pytania, z
link
iunlink
bezadd
iremove
.)źródło