Suppose I have a Network N

( i.e. just a Digraph D(A,V) with A=Arcs, V=Vertices; combined with a capacity function $c:V x V \to \mathbb{N}\cup\{0\}$ and two vertices s:=source, t:=sink singled out)

I call $f:V x V \to \mathbb{N}\cup\{0\}$ a flow if it does not exceed capacity for any pair (u,v) and the net flow at any vertex is zero expect at the source and sink where a net flow is allowed.

Now suppose I have a way of knowing the value of the maximum flow (this value just being the maximum flow $$\sum_{(s,v)\in A} f(source,v)$$ out of the source in any legal flow f. Similarly this value will equal the max total flow into the sink in any flow)

I am wondering whether there is a clever way to determine the actual flow function say $f^*$ given that I know what the maximum flow value is ?

If I had a way of knowing what the value of such a maximum flow is for any network N at no extra "cost" would this give me a more efficient way ? So far I have only used Ford Fulkerson to determine $f^*$


In "toy" examples (examples small enough to do easily by hand), knowing the maximal flow can often be used to find a flow achieving that maximum value. But in "real" examples, with hundreds of vertices and thousands of arcs, I don't think it helps at all. If it did, you could make a guess at the maximal flow, then use the clever method to find the flow with that value; if the clever method succeeds, guess a little higher, if it fails, guess a little lower, until you converge on the right answer, so you'd wind up beating Ford-Fulkerson.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.