4
$\begingroup$

I have a problem in which for a certain graph I need to compute the min cut for r times (r can be HUGE). Because each time the edge weights can be different, what i am doing (in practice) is to calculate all the edge cuts, and find the one with minimum total weight for each iteration on r.

I wonder if computing all the edge cuts is exponential.

I am using BDD and reliability theory to calculate all the edge cuts, so I am not sure what the actual complexity is there, but I want to know what would be the best complexity for finding all the edge cuts for a directed graph in theory.

Thanks,

Amir.

  • 0
    My main question is though, what is the complexity of computing all the edge cuts...2011-11-23

0 Answers 0