Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|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

 
discard

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

Browse other questions tagged or ask your own question.