Integer Solution to Synthesis of Communication Networks

This paper describes a polynomial-time algorithm for the following problem: Let r_i,j be the given requirements for all i, j ∈ {1, …, n}, with r_i,j = r_j,i for i, j. Find integer capacities c_i,j for all i, j ∈ {1, …, n} such that (considering 1, …, n as the vertices of an undirected network N, with capacities c_i,j):

(i) for for all i ≠ j there exists a flow in N from i to j of value, at least r_i,j;

(ii) ∑_i<jc_i,j 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.