16
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

O(n) time per edge addition:

$\endgroup$
  • 2
    $\begingroup$ See also: D. M. Yellin. Speeding up dynamic transitive closure for bounded degree graphs. Acta Informatica, 30:369–384, 1993. $\endgroup$ – Jeffε Aug 16 '10 at 21:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Alexandru Sep 3 '10 at 15:34
  • $\begingroup$ @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. $\endgroup$ – Antimony Mar 8 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.