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

Question

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?

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

score 10 · Answer 1 · answered Jan 12 '13 at 08:09

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.

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

1 Answers1

Linked