Premium
Topological design of centralized computer networks—formulations and algorithms
Author(s) -
Gavish Bezalel
Publication year - 1982
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230120402
Subject(s) - spanning tree , computer science , minimum spanning tree , network planning and design , tree (set theory) , steiner tree problem , variety (cybernetics) , distributed minimum spanning tree , mathematical optimization , degree (music) , decomposition , network topology , algorithm , theoretical computer science , mathematics , discrete mathematics , computer network , artificial intelligence , combinatorics , ecology , physics , acoustics , biology
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.