# What is the fastest deterministic algorithm for dynamic digraph reachability with no edge deletion?

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?

-
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
Ah.. I forgot to mention, it's digraph. My bad.... will update then. –  wei wang Nov 16 '12 at 19:43

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.