# Complexity of finding all edge cuts of a directed graph

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.

-
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