http://debianws.lexgopc.com/wiki143/index.php?action=history&feed=atom&title=Network_flow_problemNetwork flow problem - Revision history2026-05-09T20:56:07ZRevision history for this page on the wikiMediaWiki 1.43.1http://debianws.lexgopc.com/wiki143/index.php?title=Network_flow_problem&diff=2179628&oldid=previmported>Frodo Maximus: /* growthexperiments-addlink-summary-summary:2|0|0 */2025-06-22T04:50:34Z<p><span class="autocomment">growthexperiments-addlink-summary-summary:2|0|0</span></p>
<p><b>New page</b></p><div>{{short description|Class of computational problems}}<br />
In [[combinatorial optimization]], '''network flow problems''' are a class of computational problems in which the input is a [[flow network]] (a graph with numerical capacities on its edges), and the goal is to construct a [[Flow network#Flows|flow]], numerical values on each edge that respect the capacity constraints and that have incoming flow equal to outgoing flow at all vertices except for certain designated terminals.<ref name=FNbook>{{Cite book<br />
| last1 = Ahuja<br />
| first1 = Ravindra K.<br />
| last2 = Magnanti<br />
| first2 = Thomas L.<br />
| last3 = Orlin<br />
| first3 = James B.<br />
| title = Network Flows: Theory, Algorithms, and Applications<br />
| publisher = Prentice Hall<br />
| year = 1993<br />
}}</ref><br />
<br />
Specific types of network flow problems include:<br />
*The [[maximum flow problem]], in which the goal is to maximize the total amount of flow out of the source terminals and into the sink terminals<ref name="FNbook" />{{rp|166-206}}<br />
*The [[minimum-cost flow problem]], in which the edges have costs as well as capacities and the goal is to achieve a given amount of flow (or a maximum flow) that has the minimum possible cost<ref name="FNbook" />{{rp|294-356}}<br />
*The [[multi-commodity flow problem]], in which one must construct multiple flows for different commodities whose total flow amounts together respect the capacities<ref name="FNbook" />{{rp|649-694}}<br />
*[[Nowhere-zero flow]], a type of flow studied in combinatorics in which the flow amounts are restricted to a [[finite set]] of nonzero values<br />
<br />
The [[max-flow min-cut theorem]] equates the value of a maximum flow to the value of a [[minimum cut]], a partition of the vertices of the flow network that minimizes the total capacity of edges crossing from one side of the partition to the other. [[Approximate max-flow min-cut theorem]]s provide an extension of this result to multi-commodity flow problems. The [[Gomory–Hu tree]] of an undirected flow network provides a concise representation of all minimum cuts between different pairs of terminal vertices.<br />
<br />
[[Algorithm]]s for constructing flows include<br />
*[[Dinic's algorithm]], a strongly polynomial algorithm for maximum flow<ref name="FNbook" />{{rp|221-223}}<br />
*The [[Edmonds–Karp algorithm]], a faster strongly polynomial algorithm for maximum flow<br />
*The [[Ford–Fulkerson algorithm]], a [[greedy algorithm]] for maximum flow that is not in general strongly polynomial<br />
*The [[network simplex algorithm]], a method based on linear programming but specialized for network flow<ref name="FNbook" />{{rp|402-460}}<br />
*The [[out-of-kilter algorithm]] for minimum-cost flow<ref name="FNbook" />{{rp|326-331}}<br />
*The [[push–relabel maximum flow algorithm]], one of the most efficient known techniques for maximum flow<br />
<br />
Otherwise the problem can be formulated as a more conventional [[linear program]] or similar and solved using a general purpose optimization solver.<br />
<br />
== References ==<br />
{{reflist}}<br />
<br />
[[Category:Network flow problem| ]]<br />
[[Category:Graph algorithms]]<br />
[[Category:Combinatorial optimization]]<br />
[[Category:Directed graphs]]<br />
<br />
{{sia}}</div>imported>Frodo Maximus