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