Topological design of centralized computer networks—formulations and algorithms

Abstract In recent years we have evidenced an extensive effort in the development of computer communication networks. One of the important aspects of the network design process is the solution of the topological design questions involved in establishing a communication network. In this article, formulations are presented for a variety of centralized network design problems such as the minimal spanning tree problem, capacitated and degree constrained minimal spanning tree problems, The Telpak problem, and, heterogeneous network design problems. The applicability of these formulations to algorithmic development is demonstrated by developing an efficient algorithm for solving the degree constrained minimal spanning tree problem. Computational results are reported for 630 test problems. A Bender's decomposition procedure is developed and tested for the capacitated minimal spanning tree problem with less favorable results.