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 .