Editing Maximum flow problem (section)

== Extensions ==
1. In the '''[[minimum-cost flow problem]]''', each edge (''u'',v) also has a '''cost-coefficient''' ''a<sub>uv</sub>'' in addition to its capacity. If the flow through the edge is ''f<sub>uv</sub>'', then the total cost is ''a<sub>uv</sub>f<sub>uv</sub>.''  It is required to find a flow of a given size ''d'', with the smallest cost. In most variants, the cost-coefficients may be either positive or negative. There are various polynomial-time algorithms for this problem.

2. The maximum-flow problem can be augmented by '''disjunctive constraints''': a ''negative disjunctive constraint'' says that a certain pair of edges cannot simultaneously have a nonzero flow; a ''positive disjunctive constraints'' says that, in a certain pair of edges, at least one must have a nonzero flow. With negative constraints, the problem becomes [[strongly NP-hard]] even for simple networks. With positive constraints, the problem is polynomial if fractional flows are allowed, but may be [[strongly NP-hard]] when the flows must be integral.<ref>{{Cite journal|last1=Schauer|first1=Joachim|last2=Pferschy|first2=Ulrich|date=1 July 2013|title=The maximum flow problem with disjunctive constraints|journal=Journal of Combinatorial Optimization|language=en|volume=26|issue=1|pages=109–119|doi=10.1007/s10878-011-9438-7|issn=1382-6905|citeseerx=10.1.1.414.4496|s2cid=6598669}}</ref>