Osiągalność DAG z przestrzenią O (n log n) i zapytaniami w czasie O (log n)?

Dla skierowanego acykliczny wykres , istnieje struktura danych zapytań, która pozwala na osiągalności bez konieczności kwadratowej przestrzeni lub czasu, liniowy? Idealnie szukam algorytmu wykorzystującego tylko przestrzeń O (log n) na wierzchołek i czas logarytmiczny, ${\langle}V,E{\rangle}$ gdzie . $n=|V|+|E|$

Intuicyjnie wydawało mi się oczywiste, że taka struktura danych powinna istnieć, oparta na pewnym uogólnieniu standardowych algorytmów sortowania. Ale byłem zaskoczony, że nie mogłem znaleźć. Wszystko, na co natrafiłem, albo przyjmowało założenia dotyczące wykresu (np. Płaskość), albo rozwiązało trudniejszy problem w kwadratowym czasie / przestrzeni (np. Zapytania przeplatane modyfikacjami wykresu).

Strona Wikipedii dotycząca osiągalności obejmuje tylko jeden ogólny algorytm (Floyd-Warshall); reszta strony zajmuje się specjalnymi przypadkami obejmującymi założenia, takie jak wykres płaski (nie jest).

Najczęściej cytowanym papierem w tej przestrzeni wydaje się być Amortyzowana wydajność struktury danych pobierania ścieżki , ale ten i wszystkie cytowane papiery obejmują albo przestrzeń O (n ^ 2), albo czas O (n ^ 2) w celu umożliwienia aktualizacje wykresu przeplatane z zapytaniami (tj. bez wstępnego przetwarzania).

Na to pytanie nie udzielono odpowiedzi, ale dotyczy ono trudniejszego problemu zezwalania na wstawianie krawędzi przeplatane zapytaniami.

To pytanie dotyczyło trwałej (czysto funkcjonalnej) struktury danych, która nie jest tutaj wymagana. Artykuł „Zwięzłe pozy” potrzebuje przestrzeni ale spełnia zapytania czasowe ; Szukam algorytmu w gorszym czasie, w lepszej przestrzeni. $O(n^2)$ $O(1)$

Głównie szukam przyczółka w literaturze tutaj. Jeśli jest praca ankietowa na temat osiągalności wykresu, która nie spędza 99% czasu na obudowie wykresu płaskiego, to by pomogło.

graph-algorithms

— użytkownik4718
źródło

Powiązane pytanie: cstheory.stackexchange.com/questions/21503/… .

— RB

Dzięki za link RB. To pytanie i pierwsza odpowiedź nie dotyczą przestrzeni (z wyjątkiem krótkiej wzmianki o kwadracie związanej z przestrzenią, na której to pytanie oczekuje poprawy). Druga odpowiedź odnosi się do wyniku ujemnego w przypadku zapytań o odległość (tj. Wartości całkowitych lub rzeczywistych), a nie osiągalności (tj. Wartości {0,1}), które są łatwiejszym problemem. W każdym razie dzięki!

— user4718

Routing skrótów lub odniesienia wspomniane przez Christiana Sommera w powiązanym pytaniu mogą działać w praktyce. Szukasz praktycznego podejścia lub teoretycznych dolnych granic?

— András Salamon

n^{2}

$n^2$

u

$u$

v

$v$

Zobacz „etykietowanie interwałowe” i „etykietowanie 2-hopowe”, które najwyraźniej są dość skuteczne w praktyce, zarówno w czasie, jak i przestrzeni, i mogą dać ci to, czego chcesz. Ogólnie istnieje wiele schematów „indeksowania osiągalności” dla DAG.

— jkff
źródło