4
$\begingroup$

I am considering a network with the max flow problem in a particular situation. I have a set of flows which should pass a certain node A and and another set of flows which should avoid A and pass through another node B. The flows can cross each other at any other arbitrary node.

Under what category of network flow problems should this be considered?

$\endgroup$
  • $\begingroup$ Are the flows truly different, ie. do you have some unstated constraints for the flows through A and flows through B, or did you mean "set of flows" less literally and just want a variant of maximum flow where all the flows must pass through either node A or node B but not both? $\endgroup$ – Aleksi Torhamo Nov 12 '16 at 2:55
7
$\begingroup$

Flows with more than one "thing" flowing are known as "multicommodity flows".

The basic definitions assume that every thing can flow through every vertex and edge. However, the standard way of solving these problems is linear programming and you could easily modify the normal multicommodity flow program to deal with your situation, just by substituting zero for the appropriate variables.

$\endgroup$

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.