14
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Possible duplicate: cstheory.stackexchange.com/q/14343/5038 $\endgroup$ – D.W. Aug 28 '13 at 9:30
  • 5
    $\begingroup$ 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. $\endgroup$ – David Richerby Aug 28 '13 at 10:26
  • $\begingroup$ Thanks for you comments. Yes, I asked three questions, for digraph, tree and DAG. $\endgroup$ – wei wang Aug 28 '13 at 12:34
  • 1
    $\begingroup$ this might help: code-o-matic.blogspot.com/2010/07/… $\endgroup$ – saadtaame Jan 27 '15 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.