5
$\begingroup$

I have a huge DAG - e.g., the dependency graph of all packages in a linux distribution.

Suppose I'd like to make a user-friendly tool that makes it very easy to understand how to break the transitive dependency between package A and package B, and do other related queries/algorithms.

The question "how to break a transitive dependency" is answered by a min-cut.

Is there a practical indexing structure for answering all-pairs min-cut that works for large DAGs (non-ridiculous time and space complexity)? I am aware of Gomory-Hu trees (though I have not yet grasped them), but they seem to work only for undirected graphs.

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you only care about the $s-t$-min cut value or do you also want to have a min-cut for each $s-t$? $\endgroup$
    – Chao Xu
    Sep 14, 2014 at 23:11
  • $\begingroup$ @ChaoXu apparently the values only. $\endgroup$
    – Yixin Cao
    Sep 15, 2014 at 1:05
  • $\begingroup$ I would like the actual cuts, but values would be interesting too. $\endgroup$
    – jkff
    Sep 15, 2014 at 2:01

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.