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, gdzie .
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 O ( 1 ) ; Szukam algorytmu w gorszym czasie, w lepszej przestrzeni.
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.
źródło
Odpowiedzi:
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.
źródło