The network flow problem considers a graph with a set of sources and sinks and for which each edge has an assigned capacity (weight), and then asks to find the maximum flow that can be routed from to while respecting the given edge capacities. The network flow problem can be solved in time (Edmonds and Karp 1972; Skiena 1990, p. 237). It is implemented in the Wolfram Language as FindMaximumFlow[g, source, sink].
Network Flow
See also
Augmenting Path, Maximum Flow, Minimum Cut Theorem, NetworkExplore with Wolfram|Alpha
References
Edmonds, J. and Karp, R. M. "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems." J. ACM 19, 248-264, 1972.Even, S. and Tarjan, R. E. "Network Flow and Testing Graph Connectivity." SIAM J. Comput. 4, 507-518, 1975.Ford, L. R. and Fulkerson, D. R. Flows in Networks. Princeton, NJ: Princeton University Press, 1962.Gonery, R. E. and Hu, T. C. "Multiterminal Network Flows." J. SIAM 9, 551-570, 1961.Orlin, J. B. "A Faster Strongly Polynomial Minimum Cost Flow Algorithm." Proc. 20th ACM Symposium Theorem of Computing. pp. 377-387, 1988.Skiena, S. "Network Flow." §6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 237-239, 1990.Skiena, S. S. "Network Flow." §8.4.9 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 297-300, 1997.Tarjan, R. E. Data Structures and Network Algorithms. Philadelphia, PA: SIAM Press, 1983.Referenced on Wolfram|Alpha
Network FlowCite this as:
Weisstein, Eric W. "Network Flow." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NetworkFlow.html