15
$\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$
15
$\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

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.