What is the best deterministic result for maintaining the dynamic transitive closure in a directed graph with only edge insertion?

I read some papers on the dynamic transitive closure problem with both edge insertion and deletion. However, is there any better algorithms for that with only edge insertion?

  • 3
    $\begingroup$ Isn't this solved by the union-find data structure? $\endgroup$ Commented Nov 16, 2012 at 18:46
  • $\begingroup$ Is your graph directed or undirected ? @TysonWilliams is correct in that for undirected graphs with no edge deletions, you're basically just doing union find (each insertion is a UNION operation) $\endgroup$ Commented Nov 16, 2012 at 19:11
  • 2
    $\begingroup$ Ah.. I forgot to mention, it's digraph. My bad.... will update then. $\endgroup$
    – wei wang
    Commented Nov 16, 2012 at 19:43

1 Answer 1


An old paper by Italiano (G.F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(2–3):273–281, 1986.) gives a data structure that supports edge insertions in $O(n)$ amortized time and reachability queries in constant time. I'm not aware of better incremental algorithms.


Your Answer

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

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