 Maximizing Flow Through a Network With Node and Arc CapacitiesR. D. Wollmer
Transportation Science, 1968, vol. 2, issue 3, 213-232 Abstract: In many actual network flow situations, nodes as well as arcs have limited capacities. This paper presents, for such a network, an algorithm for maximizing flow from a source node to a sink node. The algorithm allows us to treat these situations without introducing artificial arcs and nodes, as has been done in the past. Eliminating the artificial arcs and nodes simplifies network analysis since it always results in half as many nodes, as well as less than half as many arcs if the original arcs are undirected. In addition, the following generalization of Ford and Fulkerson’s max-flow, min-cut theorem is presented and proven. Consider two subsets of the nodes, X and Y , whose union is the set of all network nodes and such that the source node is a member of X , and the sink node is a member of Y . Then, forming a cut set separating the source and sink are the nodes in the intersection of X and Y , and the set of all arcs ( i , j ), such that i is a member of X - Y , and j is a member of Y - X . Letting a cut set's value be the sum of the capacities of all its arcs and nodes, it follows that the maximum flow is equal to the minimum value of all cut sets separating the source and sink. Date: 1968 Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:2:y:1968:i:3:p:213-232 Access Statistics for this article More articles in Transportation Science from INFORMS Contact information at EDIRC. |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.