Integer Exact Network Synthesis Problem

S.N. Kabadi 1, J. Yan 1, 2, D. Du 1, and K. P. K. Nair 1
1 Faculty of Administration, University of New Brunswick, Fredericton, N.B. E3B5A3, Canada
2 Department of Mathematics,Department of Mathematics, Shandong University, Shandong 250101, P. R. China


Abstract     Full Text  PDF

Given an integer, non-negative, symmetric matrix $R = (r_{ij})_{n \times n}$, we consider the problem of synthesizing an undirected network $G$ on node set $V=\{1, 2, \ldots , n\}$ with non-negative, integer edge capacities such that (i) for any pair $\{i,j\}$ of distinct nodes in $V$, the value of maximum flow between $i$ and $j$ in $G$ equals exactly $r_{ij}$; and (ii) the sum of capacities of edges in $G$ is minimum. Chou and Frank claim to give an algorithm for this problem(1970, Survivable Communication Networks and the Terminal Capacity Matrix. IEEE Trans. on Circuit Theory, CT-17, 2, 192--197). But, Schrijver gives a counter-example to their claim(2003,Combinatorial optimization: Polyhedra and efficiency, Algorithms and Combinatorics 24, Springer-Verlag, New York). We present an $O(n^2)$ algorithm for the problem.