EXTRACTING MAXIMAL INFORMATION ABOUT SETS OF MINIMUM CUTS

There are two well-known, elegant, compact, and efficiently computed r epresentations of selected minimum edge cuts in a weighted, undirected graph G = (V, E) with n nodes and m edges at one extreme, the Gomory- Hu cut tree [12] represents (n/2) minimum cuts, one for each pair of n odes in G; at the other extreme, the Pioard-Queyranne DAG [24] represe nts all the minimum cuts between a single pair of nodes in G. The GH c ut tree is constructed with only n - 1 max-flow computations, and the PQ DAG is constructed with one max-flow computation, plus 0(m) additio nal time. In this paper we show how to marry these two representations , getting the best features of both. We first show that we can constru ct all (n/2) DAGs, one for each fixed pair of nodes, using only n - 1 max-flow computations as in [12], plus 0(m) time per DAG as in [24]. T his speeds up the obvious approach by a factor of n. We then apply thi s approach to an unweighted graph G, to find all the edge-connectivity cuts in G, i.e., cuts with capacity equal to the connectivity of G. M atula [22] gave a method to find one connectivity cut in 0(nm) time; w e show that 0(nm) time suffices to represent all connectivity cuts com pactly, and to list all of them explicitly. This improves the previous best time bound of 0(n2 m) [3] for listing the connectivity cuts. The connectivity cuts are central in network reliability calculations. We then show how to find all pairs of nodes that are separated by at lea st one connectivity cut in 0(nm) time.