Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.



share|cite|improve this question
What do you mean when you say you need to "compute the min cut for r times"? – Zach Langley Nov 22 '11 at 4:06
For each iteration, the weights are different, so I need to recalculate the min cut. – Amir Reza Nov 23 '11 at 20:06
My main question is though, what is the complexity of computing all the edge cuts... – Amir Reza Nov 23 '11 at 20:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.