A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
- 1 January 1957
- journal article
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 9, 210-218
- https://doi.org/10.4153/cjm-1957-024-0
Abstract
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 maximizeKeywords
This publication has 6 references indexed in Scilit:
- Maximal Flow Through a NetworkCanadian Journal of Mathematics, 1956
- Computation of maximal flows in networksNaval Research Logistics Quarterly, 1955
- The generalized simplex method for minimizing a linear form under linear inequality restraintsPacific Journal of Mathematics, 1955
- A Decomposition Theorem for Partially Ordered SetsAnnals of Mathematics, 1950
- The Distribution of a Product from Several Sources to Numerous LocalitiesJournal of Mathematics and Physics, 1941
- On Representatives of SubsetsJournal of the London Mathematical Society, 1935