Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-22T02:17:32.238Z Has data issue: false hasContentIssue false
  • English
  • Français

A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem

Published online by Cambridge University Press:  20 November 2018

L. R. Ford Jr.  and
D. R. Fulkerson
L. R. Ford Jr.
Affiliation:
Rand Corporation, Santa Monica, California
D. R. Fulkerson
Affiliation:
Rand Corporation, Santa Monica, California
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The network-flow problem, originally posed by T. Harris of the Rand Corporation, has been discussed from various viewpoints in (1; 2; 7; 16). The problem arises naturally in the study of transportation networks; it may be stated in the following way. One is given a network of directed arcs and nodes with two distinguished nodes, called source and sink, respectively. All other nodes are called intermediate. Each directed arc in the network has associated with it a nonnegative integer, its flow capacity. Source arcs may be assumed to be directed away from the source, sink arcs into the sink. Subject to the conditions that the flow in an arc is in the direction of the arc and does not exceed its capacity, and that the total flow into any intermediate node is equal to the flow out of it, it is desired to find a maximal flow from source to sink in the network, i.e., a flow which maximizes the sum of the flows in source (or sink) arcs.

Thus, if we let P1 be the source, Pn the sink, we are required to find xij (i,j =1, . . . , w) which maximize

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 9 , 1957 , pp. 210 - 218
Copyright
Copyright © Canadian Mathematical Society 1957

References

1. Dantzig, G. B. and Fulkerson, D. R., On the max flow min cut theorem of networks, Linear Inequalities and Related Systems, 215-221. Annals of Math. Study 38 (Princeton, 1956).Google Scholar
2. Dantzig, G. B. and Fulkerson, D. R., Computation of maximal flows in networks, Naval Research Logistics Quarterly, 2 (1955), 277–283.Google Scholar
3. Dantzig, G. B., Orden, A., and Wolfe, P., The generalized simplex method for minimizing a linear form under linear inequality constraints, Pacific J. Math., 5 (1955), 183–195.Google Scholar
4. Dantzig, G. B., Application of the simplex method to a transportation problem, Activity Analysis of Production and Allocation, 359–373. Cowles Commission Monograph 13 (New York, 1951).Google Scholar
5. Dilworth, R. P., A decomposition theorem for partially ordered sets, Annals Math., 51 (1950), 161–166.Google Scholar
6. Egerváry, E., Matrixok kombinatorius tulajdonságáirol, Mat. és Fiz. Lapok 38 (1931), 16–28 (translated as On combinatorial properties of matrices, by H. W. Kuhn, Office of Naval Research Logistics Project Report (Princeton, 1953)).Google Scholar
7. Ford, L. R. Jr. and Fulkerson, D. R., Maximal flow through a network, Can. J. Math., 8 (1956), 399–404.Google Scholar
8. Fulkerson, D. R., Note on Dilworth's chain decomposition theorem for partially ordered sets, Proc. Amer. Math. Soc, 7 (1956), 701–702.Google Scholar
9. Gale, D., A theorem onflows in networks, to appear in Pacific J. Math.Google Scholar
10. Gale, D., Kuhn, H. W., and Tucker, A. W., Linear programming and the theory of games, Activity Analysis of Production and Allocation, 317-329. Cowles Commission Monograph 13 (New York, 1951).Google Scholar
11. Hall, P., On representatives of subsets, Jour. London Math. Soc, 10 (1935), 26–30.Google Scholar
12. Hitchcock, F. L., The distribution of a product from several sources to numerous localities, Jour. Math. Phys., 20 (1941), 224–230.Google Scholar
13. König, D., Theorie der endlichen und unendlichen Graphen (Chelsea, New York, 1950).Google Scholar
14. Koopmans, T. C. and Reiter, S., A model of transportation, Activity Analysis of Production and Allocation, 222-259. Cowles Commission Monograph 13 (New York, 1951).Google Scholar
15. Kuhn, H. W., A combinatorial algorithm for the assignment problem. Issue 11 of Logistics Papers, George Washington University Logistics Research Project, 1954.Google Scholar
16. Robacker, J. T., On network theory. Rand Corp., Research Memorandum RM-1498, 1955.Google Scholar