Networks · 1982 · 259 citations · 28 references
ComputingComputer ScienceComputer NetworksOptimizationTopologyCombinatorial OptimizationCommunication NetworksGraph AlgorithmsNetwork DesignNetwork OptimizationNetwork TopologyCentralized Communication TopologyCentralized Network ArchitectureMinimum Spanning Tree AlgorithmsMinimum Spanning Tree ProblemNetwork Design ProblemsNetwork Topology DesignTopology DesignTopology Synthesis
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 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.
28
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
The Traveling-Salesman Problem and Minimum Spanning Trees
Michael Held, Richard M. Karp · Operations Research · 1970 · 1.4K citations