<p>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.</p>

CC BY-SA 3.0
2013-01-12T08:09:01.767Z
2013-01-12T08:09:01.767Z
virgi
<p>What is the best deterministic result for maintaining the dynamic transitive closure in a directed graph with only edge insertion?</p>

<p>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?</p>

CC BY-SA 3.0
2012-11-16T18:46:50.813Z
Isn't this solved by the union-find data structure?
Tyson Williams
CC BY-SA 3.0
2012-11-16T19:11:16.443Z
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
CC BY-SA 3.0
2012-11-16T19:43:53.130Z
Ah.. I forgot to mention, it's digraph. My bad.... will update then.
wei wang
<ds.algorithms><graph-theory><graph-algorithms><dynamic-algorithms>
What is the fastest deterministic algorithm for dynamic digraph reachability with no edge deletion?
wei wang
# What is the fastest deterministic algorithm for dynamic digraph reachability with no edge deletion?

(Asked by: username_0 on 2012-11-16)

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?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, dynamic-algorithms
> **Comments:**
> **username_1**: Isn't this solved by the union-find data structure?  
> **username_2**: 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)  
> **username_0**: Ah.. I forgot to mention, it's digraph. My bad.... will update then.  

---

## 1 answers

### Answer by username_3 on 2013-01-12. Score: 10

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.


---

