I have built a max network flow graph that carries certain amount of people from a source to a destination. Now, I'd like to attach a lower bound $l_(e_)$ constraint to each edge $e$. But I don't know what algorithm to use and how to analyze its complexity. Here's the graph:

enter image description here



There's a very simple reduction from that problem to the maximum flow problem. This is simply called "maximum flow with edge demands".

  • $\begingroup$ The link given is for checking if the flow is feasible, i.e. minimum flow. $\endgroup$ – evil999man Mar 26 '17 at 16:29

The formal prolem is called: "Maximum Flows with Edge Demands" and it's available here: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/25-maxflowext.pdf

  • 1
    $\begingroup$ Welcome to CS.SE! This duplicates an existing answer. I'm not sure there is much value in repeating the information already available in an existing answer without adding anything new. If the purpose was to provide an updated link, a better way to do that is by suggesting an edit (using the 'suggest an edit' link under the answer) to update the link. $\endgroup$ – D.W. Nov 26 '18 at 21:24

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.