Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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^*$

share|cite|improve this question

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.

share|cite|improve this answer

Your Answer


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

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