17
$\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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
17
$\begingroup$

O(n) time per edge addition:

Improve this answer
$\endgroup$
4
  • 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, 2010 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, 2010 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, 2020 at 20:49
  • $\begingroup$ Italiano algorithm is really good. Super fast, easy to understand and implement. $\endgroup$
    – Mu-Tsun Tsai
    Oct 6, 2021 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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