A decomposition algorithm for multi-terminal network flows (Q1085042)

There is a well-known solution to the problem of computing the maximum flow between all terminals in a graph of m undirected edges and n vertices. It has been provided by Hu in a classical paper, and requires n-1 maximum flow calculations resulting in the so-called cut tree for the network. Assuming that \(m=O(n^ 2)\), each maximum flow calculation can be done in \(O(n^ 3)\) time, and the total complexity of the algorithms is \(O(n^ 4).\) This may be too large for large networks. In this case, the authors propose another method that relies on the fact that large networks can often be decomposed into components, for which maximum flow calculations can be made more efficiently. The components in question are the so- called tri-connected components, in the sense defined by \textit{J. E. Hopcroft} and \textit{R. E. Tarjan} [SIAM J. Computing 2, 135--158 (1973; Zbl 0281.05111)]. The algorithm is as follows. (1) Decompose the network into its tri-connected components. (2) From these components, construct a rooted tree, called the component tree. (3) For each component, starting from the leaves of the tree, compute the maximum flow, using only the edges in the component. (4) Proceeding upwards, find the corresponding cut-tree for the root. Then, traverse the component tree downward again to obtain the cut-tree of all the vertices. The paper gives a description of the decomposition algorithm, as well as an expression for its complexity. If the network has p tri-connected components of size O(n/p), then it is \(O(n^ 4/p^ 3+n^ 2)\), a substantial improvement over the classical method when p is large.