Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
Isn't this solved by the union-find data structure? –  Tyson Williams Nov 16 '12 at 18:46
    
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) –  Suresh Venkat Nov 16 '12 at 19:11
1  
Ah.. I forgot to mention, it's digraph. My bad.... will update then. –  wei wang Nov 16 '12 at 19:43
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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