<p>As the title. The incremental algorithm maintains the reachability information  of a DAG when it undergoes a series of edge insertions (but no deletions). And the algorithm supports constant query (if node u reaches node v) time.</p>

<p>It takes amortized O(n) time for each edge insertion (G.F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(2–3):273–281, 1986.) on general directed graphs. Is it possible to do it faster on DAGs?</p>

CC BY-SA 3.0
2013-08-28T09:30:34.990Z
Possible duplicate: http://cstheory.stackexchange.com/q/14343/5038
D.W.
CC BY-SA 3.0
2013-08-28T10:26:54.490Z
Not a duplicate: the linked question is the same person asking about general directed graphs and that thread says nothing about DAGs. The second paragraph of the present question summarizes the answer to the first one.
David Richerby
CC BY-SA 3.0
2013-08-28T12:34:32.927Z
Thanks for you comments. Yes, I asked three questions, for digraph, tree and DAG.
wei wang
CC BY-SA 3.0
2015-01-27T22:37:06.510Z
this might help: http://code-o-matic.blogspot.com/2010/07/graph-reachability-transitive-closures.html
mrk
<graph-theory><graph-algorithms><dynamic-algorithms>
What is the fastest deterministic algorithm for incremental DAG reachability?
wei wang
# What is the fastest deterministic algorithm for incremental DAG reachability?

(Asked by: username_0 on 2013-08-28)

As the title. The incremental algorithm maintains the reachability information of a DAG when it undergoes a series of edge insertions (but no deletions). And the algorithm supports constant query (if node u reaches node v) time.

It takes amortized O(n) time for each edge insertion (G.F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(2–3):273–281, 1986.) on general directed graphs. Is it possible to do it faster on DAGs?

**Tags:** graph-theory, graph-algorithms, dynamic-algorithms
> **Comments:**
> **username_1**: Possible duplicate: http://cstheory.stackexchange.com/q/14343/5038  
> **username_2**: Not a duplicate: the linked question is the same person asking about general directed graphs and that thread says nothing about DAGs. The second paragraph of the present question summarizes the answer to the first one.  
> **username_0**: Thanks for you comments. Yes, I asked three questions, for digraph, tree and DAG.  
> **username_3**: this might help: http://code-o-matic.blogspot.com/2010/07/graph-reachability-transitive-closures.html  

---

## 0 answers

