# 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->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.

• See also: D. M. Yellin. Speeding up dynamic transitive closure for bounded degree graphs. Acta Informatica, 30:369–384, 1993. Aug 16, 2010 at 21:23
• First paper provides two important operations from transitive closure, but I need a third one: iterating through all accessible nodes. The second paper is good, though. Sep 3, 2010 at 15:34
• @Alexandru The first paper provides a nxn table which lets you determine if one node is reachable from another in constant time. So to iterate over all nodes reachable from a given node, just iterate that column and see which pointers are non-null. Or you could just iterate the descendant tree, which is O(k) where k is the number of reachable nodes. Mar 8, 2020 at 20:49
• Italiano algorithm is really good. Super fast, easy to understand and implement. Oct 6, 2021 at 14:37