Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-22T07:09:03.273Z Has data issue: false hasContentIssue false
  • English
  • Français

Network Flow and Systems of Representatives

Published online by Cambridge University Press:  20 November 2018

L. R. Ford Jr.  and
D. R. Fulkerson
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 theory developed for the study of flows in networks (2; 3; 4; 5; 6; 7) sometimes provides a useful tool for dealing with certain kinds of combinatorial problems, as has been previously indicated in (3; 4; 6; 7). In particular, Hall-type theorems for the existence of systems of distinct representatives which contain a prescribed set of marginal elements (10; 11), or, more generally, whose intersection with each member of a given partition of the fundamental set has a cardinality between prescribed lower and upper bounds (9), can be obtained in this way (7).

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 10 , 1958 , pp. 78 - 84
Copyright
Copyright © Canadian Mathematical Society 1958

References

1. 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
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., On the min cut max flow theorem of networks, Annals of Mathematics Study No. 38, Linear Inequalities and Related Systems, ed. H. W. Kuhn and A. W. Tucker (Princeton, 1956), 215-221.Google Scholar
4. Ford, Jr. L. R. , 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-218.Google Scholar
5. Ford,Jr. L. R. , Maximal flow through a network, Can. J. Math., 8 (1956), 399-404.Google Scholar
6. Gale, D., A Theorem on flows in networks, RAND Corporation, Research Memorandum RM-1737, 1956 (to appear in Pacific J. Math.).Google Scholar
7. Gale, D. and Hoffman, A., Circulation in networks (unpublished notes).Google Scholar
8. Hall, P., On representatives of subsets, J. Lond. Math. Soc, 10 (1935), 26-30.Google Scholar
9. Hoffman, A. J. and Kuhn, H. W., On systems of distinct representatives, Annals of Mathematics Study, No. 38, Linear Inequalities and Related Systems, ed. H. W. Kuhn and A. W. Tucker (Princeton, 1956), 199-206.Google Scholar
10. Hoffman, A. J., Systems of distinct representatives and linear programming, Amer. Math. Monthly, 68 (1956), 455-460.Google Scholar
11. Mann, H. B. and Ryser, H. J., Systems of distinct representatives, Amer. Math. Monthly, 60 (1953), 397-401.Google Scholar