Very Simple Methods for All Pairs Network Flow Analysis
SIAM J. Comput., 19 (1):
143--155 (February 1990)DOI: 10.1137/0219009
Abstract
A very simple algorithm for the classical problem of computing the maximum network flow value between every pair of nodes in an undirected, capacitated n node graph is presented; as in the well-known Gomory–Hu method, the method given here uses only $n - 1$ maximum flow computations. Our algorithm is implemented by adding only five simple lines of code to any program that produces a minimum cut; a program to produce an equivalent flow tree, which is a compact representation of the flow values, is obtained by adding only three simple lines of code to any program producing a minimum cut. A very simple version of the Gomory–Hu cut tree method that finds one minimum cut for every pair of nodes is also derived, and it is shown that the seemingly fundamental operation of that method, node contraction, is not needed, nor must crossing cuts be avoided. As a result, this version of the Gomory–Hu method is implemented by adding less than ten simple lines of code to any program that produces a minimum cut. The algorithms in this paper demonstrate that a cut tree of graph G can be computed with $n - 1$ calls to an oracle that alone knows G, and that, when given two nodes s and t, returns any arbitrary minimum $(s, t)$ cut and its value.