Record:   Prev Next
Author CAPALDI, ERIC ALAN
Title ALL-PAIRS MAXIMUM FLOWS IN NETWORKS
Descript 153 p
Note Source: Dissertation Abstracts International, Volume: 42-01, Section: B, page: 0345
Thesis (Ph.D.)--University of California, Berkeley, 1980
The computation of all the max flows in a network may be done by simply finding individual max flows for every possible source and sink. However, this process is shown to be extremely wasteful in the sense that much of the information generated in computing any one max flow can easily apply toward computing other max flows
In section I, the concept of condensed networks is introduced; these are networks in which an entire set of nodes is considered as a single node. Relationships between max flows in condensed and ordinary networks are explored using the max flow/min cut concepts. Two flows in condensed graphs, a condensed and an ordinary flow, and two ordinary flows may each produce other max flows
Symmetric and Pseudo-Symmetric networks are considered next. These are networks in which the capacity of any cut (S,T) equals the capacity of the cut (T,S). For such networks, an undirected and capacitated tree, (called a cut-tree), on the nodes of the network is shown to exist. This cut-tree has the property that for any two nodes, one may remove the arc of the tree along the path connecting the nodes which has minimum capacity, and the two components induced in the tree form a min cut separating these nodes which has capacity equal to that of the removed arc. Constructive proofs of the existance of such a structure for pseudo-symmetric networks with capacities and lower bounds, (which admit a feasible circulation), are given in sections I and II. A cyclical decompositon of such networks is given in appendix B, by which one may take advantage of these structures to create two pseudo-symmetric networks to approximate all the max flows in an ordinary network
Computationally oriented algorithms for finding the max flows between all pairs of nodes in both ordinary and pseudo-symmetric networks are given in section III. For pseudo-symmetric networks, a method is given by which one may compute n - 1 max flows (where n is the number of nodes) and do n - 1 simple labellings to produce a cut-tree. Another method, first presented by Gomory and Hu, is presented in which n - 1 max flows are done in smaller networks to produce the cut-tree. The Pseudo-Symmetric Flows algorithm uses this tree to compute all the max flows in an efficient manner. The Unsymmetric Flows algorithm uses many of the same concepts to find all the max flows in ordinary networks. Both of these methods can be implemented with any routine for finding individual max flows
An efficient utilization of linear programming is possible using the dual of the max flow problem. Given a min cut separating a source from several sinks, a single basis which is optimal in objective value for all these pairs of nodes is produced. Using this starting basis, one may quickly solve the max flow problem for all these pairs
Augmenting path implementations are also considered. A special labelling scheme, which when applied to an ordinary network leads to a max flow to (or from) a condensed node, is presented. Applications to the Flows algorithms are given in which each of these "half-flows" suffices for one or more max flows in the original network, with corresponding computational savings
School code: 0028
Host Item Dissertation Abstracts International 42-01B
Subject Operations Research
0796
Alt Author University of California, Berkeley
Record:   Prev Next