Online transitive closure better than O(N^2) per edge addition I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this: 

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


For O(N^2) edges this translates in a total time complexity of O(N^4) which much worse than, for example, Floyd-Warshall.
O(n) time per edge addition:


G. F. Italiano (1986): Amortized efficiency of a path retrieval data structure, Theoretical Computer Science 48, 273–281.
J. A. La Poutré and J. van Leeuwen (1988): Maintenance of transitive closures and transitive reductions of graphs, Proc. WG 1987.