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.