Optimization of connecting two communication networks subject to a reliability constraint

This paper considers optimization of two networks with a reliability constraint The objective is to find some links to connect two networks, at a minimal cost, under the constraint that the system reliability of the resultant network is not less than a given level. A decomposition method based on branch and bound is used for solving the problem. In order to speed up the solution procedure, an upper bound on system reliability in terms of node degrees is applied. In particular, when the threshold P-0 is large enough, a new algorithm, the cut tree algorithm, can more effectively give an optimal solution. Copyright (C) 1966 Elsevier Science Ltd.