MaximumFlow-min cut on directed graph

Sep 14, 2009 at 2:38 PM
Edited Sep 16, 2009 at 10:48 PM

hello, i known that this subject is a little bit related to the one post before, but my question is different. Is there a way to recover the minimum cut directly from the maximum flow algorith

ie: the maximum flow algorith give a list of residual capacities and the maximum flow value, from those is that possible to get the minimum cut directly and if yes how?

here is what i have to do for now :

1- apply a maximum flow algorith

2- from the residual capacities i create a new graph (edge that have 0 of residual capacities, or that were not existing in the original graph are not added)

3-on this new graph composed of Vertex named V i apply the StronglyConnectedComponentsAlgorithm to find all vertex related to the source vertex (i ll name them X)

4-from this group of vertex i apply the cut in checking all    (X,V-X) possibilities

thz in advance