Problem

Mam nieukierunkowany wykres (z wieloma krawędziami), który z czasem się zmieni, węzły i krawędzie można wstawiać i usuwać. Przy każdej modyfikacji wykresu muszę aktualizować połączone elementy tego wykresu.

Nieruchomości

Dodatkowe właściwości polegają na tym, że żadne dwa składniki nigdy nie zostaną ponownie połączone. Oczywiście wykres może mieć dowolne cykle (w przeciwnym razie rozwiązanie byłoby trywialne). Jeśli krawędź nie zawiera węzła n , nigdy nie przyjmie tego węzła. Jednak jeśli n ∈ e , może zmienić się na n ∉ e .$e$$n$$n \in e$$n \notin e$

Podejścia

Do tej pory mam dwa możliwe podejścia, ale jak zobaczycie, są one okropne:

Powolny bez stanu

Mogę za każdym razem przeszukiwać (dfs / bfs) wykres, zaczynając od zmodyfikowanych elementów. Oszczędza to miejsce, ale jest wolne, ponieważ dla każdej modyfikacji mamy O (n + m).

Podejście stanowe szybkie (-er) (?)

Mogę przechowywać wszystkie możliwe ścieżki dla każdego węzła do wszystkich możliwych węzłów, ale jeśli zobaczę to poprawnie, zajmie to pamięć O (n ^ 4). Ale nie jestem pewien, jak poprawia się środowisko wykonawcze (jeśli w ogóle istnieje, ponieważ muszę aktualizować informacje dla każdego węzła w tym samym komponencie).

Pytanie

Czy masz jakieś wskazówki, w jaki sposób mogę dowiedzieć się więcej na temat tego problemu lub może algorytmów, na których mogę bazować?

Uwaga

Jeśli nastąpiłaby znaczna poprawa czasu wykonywania / pamięci, mógłbym żyć z nieoptymalnym rozwiązaniem, które czasami mówi, że dwa składniki są jednym, ale oczywiście wolałbym optymalne rozwiązanie.

Istnieje kilka struktur danych, które obsługują wstawianie krawędzi, usuwanie krawędzi i zapytania dotyczące łączności (czy te dwa wierzchołki są w tym samym połączonym składniku?) W czasie polilogarytmicznym.

• Monika R. Henzinger i Valerie King. Randomizowane w pełni dynamiczne algorytmy grafowe z czasem polilogarytmicznym na operację . Journal of the ACM 46 (4): 502–516, 1999.

• Jacob Holm, Kristian de Lichtenberg i Mikkel Thorup. Poli-logarytmiczne deterministyczne w pełni dynamiczne algorytmy dla łączności, minimalnego drzewa opinającego , 2-krawędziowego i biconnectivity , Journal of ACM 48 (4): 723–760, 2001.

• Mikkel Thorup. Niemal optymalna, w pełni dynamiczna łączność z grafem . Proc. 32. STOC 343–350, 2000.

Myślę, że szukasz algorytmu grafu dynamicznego do dekompozycji połączonych komponentów. Algorytm Holma, de Lichtenberga i Thorupa [HLT01] ma amortyzowany czas polilogarytmiczny przy każdej aktualizacji krawędzi. Dawno nie patrzyłem na ten problem już dawno, więc prawdopodobnie postęp jest bardziej aktualny.

[HLT01] Jacob Holm, Kristian de Lichtenberg i Mikkel Thorup. Poli-logarytmiczne deterministyczne w pełni dynamiczne algorytmy dla łączności, minimalnego drzewa opinającego, 2-krawędziowego i biconnectivity. Journal of the ACM , 48 (4): 723–760, lipiec 2001. http://doi.acm.org/10.1145/502090.502095

(Na razie pozwólcie, że pozostanę przy zapytaniach dotyczących łączności, które niestety mogą być niewystarczające dla twojej aplikacji).

Wiele wcześniejszych prac nad problemem dynamicznej łączności dotyczy modelu aktualizacji krawędzi: zakładasz, że liczba wierzchołków jest stała i możesz wstawiać i / lub usuwać krawędzie podczas tworzenia zapytań. Jeśli możesz tylko wstawić (usunąć), będzie to przyrostowe (malejące). Jeśli możesz zrobić jedno i drugie, jest to w pełni dynamiczne. Prace Thorupa, jak wskazał JeffE (i ja w komentarzu), są przeznaczone do aktualizacji krawędzi.

AFAIK, społeczność teorii CS dopiero zaczyna przyglądać się aktualizacjom wierzchołków dla ogólnych wykresów. Chan, Pătraşcu i Roditty przeprowadzili w FOCS 2008 przełomowe prace w tej sprawie. Zobacz ten link, aby zobaczyć najnowszą (wrzesień 2010 r.) Wersję i odnośniki do niej.