LEADER 00000nam  2200325   4500 
001    AAI8112981 
005    20111011081603.5 
008    111011s1980    ||||||||||||||||| ||eng d 
035    (UMI)AAI8112981 
040    UMI|cUMI 
100 1  CAPALDI, ERIC ALAN 
245 10 ALL-PAIRS MAXIMUM FLOWS IN NETWORKS 
300    153 p 
500    Source: Dissertation Abstracts International, Volume: 42-
       01, Section: B, page: 0345 
502    Thesis (Ph.D.)--University of California, Berkeley, 1980 
520    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 
520    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 
520    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 
520    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 
520    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 
520    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 
590    School code: 0028 
650  4 Operations Research 
690    0796 
710 2  University of California, Berkeley 
773 0  |tDissertation Abstracts International|g42-01B 
856 40 |uhttp://pqdd.sinica.edu.tw/twdaoapp/servlet/
       advanced?query=8112981