Topological design of centralized computer networks—formulations and algorithms

Bezalel Gavish

Networks · 1982 · 259 citations · 28 references

Concepts

TL;DR

Computer communication networks have seen extensive development, with topological design being a key aspect of the network design process. The article presents formulations for various centralized network design problems, including minimal spanning tree, capacitated and degree‑constrained variants, the Telpak problem, and heterogeneous network design. The authors develop and test these formulations, report computational results on 630 test problems, and apply a Bender’s decomposition procedure to the capacitated minimal spanning tree problem. An efficient algorithm for the degree‑constrained minimal spanning tree problem demonstrates the practical applicability of the proposed formulations.

Abstract

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.

References

28