Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.