Descript 
153 p 
Note 
Source: Dissertation Abstracts International, Volume: 4201, 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 PseudoSymmetric 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 cuttree), on the nodes of the network is shown to exist. This cuttree 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 pseudosymmetric 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 pseudosymmetric 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 pseudosymmetric networks are given in section III. For pseudosymmetric 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 cuttree. Another method, first presented by Gomory and Hu, is presented in which n  1 max flows are done in smaller networks to produce the cuttree. The PseudoSymmetric 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 "halfflows" suffices for one or more max flows in the original network, with corresponding computational savings 

School code: 0028 
Host Item 
Dissertation Abstracts International 4201B

Subject 
Operations Research


0796

Alt Author 
University of California, Berkeley

