Integer solution to synthesis of communication networks

This paper describes a polynomial-time algorithm for the following problem: Let be the given requirements for all , with for all i, j. Find integer capacities for all such that (considering as the vertices of an undirected network N, with capacities ci,j): (i) for all there exists a flow in N from i to j of value, at least is minimized. This is the integer version of Gomory and Hu's problem to synthesize an undirected network. It is shown that rounding holds when there is no node with unit potential.