16

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?

wei wang
  • 519
  • 2
  • 7
  • Possible duplicate: http://cstheory.stackexchange.com/q/14343/5038 – D.W. Aug 28 '13 at 09:30
  • 6
    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 Aug 28 '13 at 10:26
  • Thanks for you comments. Yes, I asked three questions, for digraph, tree and DAG. – wei wang Aug 28 '13 at 12:34
  • 1
    this might help: http://code-o-matic.blogspot.com/2010/07/graph-reachability-transitive-closures.html – mrk Jan 27 '15 at 22:37

0 Answers0