17
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Isn't this solved by the union-find data structure? $\endgroup$ – Tyson Williams Nov 16 '12 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$ – Suresh Venkat Nov 16 '12 at 19:11
  • 1
    $\begingroup$ Ah.. I forgot to mention, it's digraph. My bad.... will update then. $\endgroup$ – wei wang Nov 16 '12 at 19:43
10
$\begingroup$

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.

Improve this answer
$\endgroup$

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.