Multi-terminal maximum flows in node-capacitated networks

AbstractThe problem of finding the maximum flows between each pair of nodes in a subset of k nodes of a node- and arc-capacitated undirected network is studied. Gomory and Hu (1961) showed that in the arc-capacitated case, it suffices to solve only k−1 of the k(k−1)2 required maximum-flow problems. The node-capcitated case apparently cannot be reduced to the arc-capacitated case, although the converse is possible. The purpose of this paper is to extend Gomory and Hu's result to the general node- and arc-capacitated case