17

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.

Jukka Suomela
  • 11,500
  • 2
  • 53
  • 116
Alexandru
  • 696
  • 3
  • 16

1 Answers1

17

O(n) time per edge addition:

Jukka Suomela
  • 11,500
  • 2
  • 53
  • 116
  • 2
    See also: D. M. Yellin. Speeding up dynamic transitive closure for bounded degree graphs. Acta Informatica, 30:369–384, 1993. – Jeffε Aug 16 '10 at 21:23
  • 1
    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. – Alexandru Sep 03 '10 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. – Antimony Mar 08 '20 at 20:49
  • Italiano algorithm is really good. Super fast, easy to understand and implement. – Mu-Tsun Tsai Oct 06 '21 at 14:37