16
$\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?

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

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.