Zamykanie przechodnie online lepiej niż O (N ^ 2) na dodanie krawędzi

Szukam algorytmu online, aby utrzymać przechodnie przechodzenie ukierunkowanego wykresu acyklicznego o złożoności czasowej mniejszej niż O (N ^ 2) na dodanie krawędzi. Mój obecny algorytm wygląda następująco:

For every new edge u->v connect all nodes in Pred(u) \cup { u } with all nodes in Succ(v) \ \cup { v }.

W przypadku krawędzi O (N ^ 2) przekłada się to na całkowitą złożoność czasową O (N ^ 4), która jest znacznie gorsza niż na przykład Floyda-Warshalla .

ds.algorithms graph-theory ds.data-structures transitive-closure Alexandru
źródło

Odpowiedzi:

O (n) czas na dodanie krawędzi:

GF Italiano (1986): Amortyzowana wydajność struktury danych pobierania ścieżki , Theoretical Computer Science 48, 273–281.
JA La Poutré i J. van Leeuwen (1988): Utrzymanie przechodnie przechodzenia i przechodnie przechodzenie grafów , Proc. WG 1987 .

Jukka Suomela
źródło

Zobacz także: DM Yellin. Przyspieszenie dynamicznego zamykania przechodniego dla wykresów o ograniczonym stopniu. Acta Informatica, 30: 369–384, 1993.

Jeffε

Pierwszy artykuł zawiera dwie ważne operacje od zamknięcia przechodniego, ale potrzebuję trzeciej: iteracji przez wszystkie dostępne węzły. Drugi artykuł jest jednak dobry.

Alexandru