Premium
The Capacitated Minimum Spanning Tree
Author(s) -
Chandy K. M.,
Lo Tachen
Publication year - 1973
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.3230030204
Subject(s) - spanning tree , minimum spanning tree , distributed minimum spanning tree , tree (set theory) , computer science , minimum degree spanning tree , mathematical optimization , steiner tree problem , euclidean minimum spanning tree , mathematics , combinatorics , algorithm
The capacitated minimum spanning tree is an offspring of the minimum spanning tree and network flow problems. It has application in the design of multipoint linkages in elementary teleprocessing tree networks. Some theorems are used in conjunction with Little's branch and bound algorithm to obtain optimal solutions. Computational results are provided to show that the problem is tractable.