My question is: in a DAG, each edge has a different value of capacity, we can assume these capacities are integers multiples of the total number of edges. Also, sometimes we can have many minimum cuts, but these cuts have a different number of edges, how can we know which cut has the maximal number of edges?
4
-
$\begingroup$ Remove $\epsilon$ from each weight, for small enough $\epsilon$. $\endgroup$– Yuval FilmusCommented Sep 28, 2019 at 23:03
-
4$\begingroup$ Possible duplicate of Minimum-cut with minimum number of edges $\endgroup$– Yuval FilmusCommented Sep 28, 2019 at 23:04
-
$\begingroup$ @YuvalFilmus Thanks for the response, I have seen this link to find the minimum cut with the minimum number of edges. By removing small e, do you mean C * (|E| + 1) + 1 instead of + 1, I need to change it into C * (|E| + 1) - 1? $\endgroup$– AutoEncoderCommented Sep 29, 2019 at 0:34
-
$\begingroup$ You can do it in various ways. I’ll let you work it out. $\endgroup$– Yuval FilmusCommented Sep 29, 2019 at 7:01
Add a comment
|