Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-19T21:55:20.680Z Has data issue: false hasContentIssue false
  • English
  • Français

A Network-Flow Feasibility Theorem and Combinatorial Applications

Published online by Cambridge University Press:  20 November 2018

D. R. Fulkerson
D. R. Fulkerson*
Affiliation:
The Rand Corporation
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.

There are a number of interesting theorems, relative to capacitated networks, that give necessary and sufficient conditions for the existence of flows satisfying constraints of various kinds. Typical of these are the supply-demand theorem due to Gale (4), which states a condition for the existence of a flow satisfying demands at certain nodes from supplies at other nodes, and the Hoffman circulation theorem (received by the present author in private communication), which states a condition for the existence of a circulatory flow in a network in which each arc has associated with it not only an upper bound for the arc flow, but a lower bound as well. If the constraints on flows are integral (for example, if the bounds on arc flows for the circulation theorem are integers), it is also true that integral flows meeting the requirements exist provided any flow does so.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 11 , 1959 , pp. 440 - 451
Copyright
Copyright © Canadian Mathematical Society 1959

References

1. Ford, L. R. Jr., and Fulkerson, D. R., Maximal flow through a network, Can. J. Math., 8 (1956), 399–404.Google Scholar
2. Ford, L. R. Jr., and Fulkerson, D. R., A simple algorithm for finding maximal network flows and an application to the Hitchcock problem, Can. J. Math., 9 (1957), 210-18.Google Scholar
3. Ford, L. R. Jr., and Fulkerson, D. R. Network flow and systems of representatives, Can. J. Math., 10 (1958), 78–85.Google Scholar
4. Gale, D., A theorem onflows in networks, Pac. J. Math., 7 (1957), 1073-82.Google Scholar
5. Hoffman, A. J. and Kuhn, H. W., On systems of distinct representatives, in H. W. Kuhn and A. W. Tucker (eds.), Linear inequalities and related systems, Annals of Mathematics Study No. 38, (Princeton, 1956).Google Scholar
6. Ore, O., Studies on directed graphs, I, Ann. Math., 63 (1956), 383–406.Google Scholar
7. Ore, O., Studies on directed graphs, II, Ann. Math., 64 (1956), 142–53.Google Scholar
8. Ore, O., Graphs and subgraphs, Trans. Amer. Math. Soc, 84 (1957), 109–37.Google Scholar
9. Ryser, H. J., Combinatorial properties of matrices of zeros and ones, Can. J. Math., 9 (1957), 371–7.Google Scholar
10. Tutte, W. T., The factorization of linear graphs, J. Lond. Math. Soc, 22 (1947), 107–11.Google Scholar
11. Tutte, W. T., The 1-factors of oriented graphs, Proc. Amer. Math. Soc, 4 (1953), 922-30.Google Scholar
12. Tutte, W. T., The factors of graphs, Can. J. Math., 4 (1952), 314–29.Google Scholar