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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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.

share|cite|improve this answer

Your Answer


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.