There are two well-known, elegant, compact, and efficiently computed representations 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 represents (n/2) minimum cuts, one for each pair of nodes in G; at the other extreme, the Pioard-Queyranne DAG represents all the minimum cuts between a single pair of nodes in G. The GH cut tree is constructed with only n-1 max-flow computations, and the PQ DAG is constructed with one max-flow computation, plus O(m) additional time. In this paper the authors show how to marry these two representations, getting the best features of both. It is first shown that all (n/2) DAGS can be constructed, one for each fixed pair of nodes, using only n-1 max-flow computations, plus O(m) time per DAG. This speeds up the obvious approach by a factor of n. This approach is then applied 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. Matula gave a method to find one connectivity cut in O(nm) time; the authors show that O(nm) time suffices to represent all connectivity cuts compactly, and to list all of them explicitly. This improves the previous best time bound of O(n2m) for listing the connectivity cuts. The connectivity cuts are central in network reliability calculations. The authors then show how to find all pairs of nodes that are separated by at least one connectivity cut in O(nm) time.
