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 in {1,2,...,n}. Find integer capacities c(i,j) for all 
i,j in {1,2,...,n} such that 9considering 1,2,...,n as vertices of an undirected network N with 
capacities c(i,j)): (i) for all i different from j there exists a flow in N from i to j of value
at least r(i,j); (ii)the sum of c(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.