TOPICS
Search

Network Flow


The network flow problem considers a graph G with a set of sources S and sinks T and for which each edge has an assigned capacity (weight), and then asks to find the maximum flow that can be routed from S to T while respecting the given edge capacities. The network flow problem can be solved in time O(n^3) (Edmonds and Karp 1972; Skiena 1990, p. 237). It is implemented in the Wolfram Language as FindMaximumFlow[g, source, sink].


See also

Augmenting Path, Maximum Flow, Minimum Cut Theorem, Network

Explore 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 Flow

Cite this as:

Weisstein, Eric W. "Network Flow." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NetworkFlow.html

Subject classifications