Optimum Communication Spanning Trees.
Abstract
Trees(Mathematics), Spanning treesGiven a set of nodes (N sub i) (i = 1,2,...,n) which may represent cities and a set of requirements (r sub ij) which may represent the number of telephone calls between (N sub i) and (N sub j), the problem is to build a spanning tree connecting these n nodes such that the total cost of communication of the spanning tree is a minimum among all spanning trees. The cost of communication for a pair of nodes is (r sub ij) multiplied by the sum of the distances of arcs which form the unique path connecting (N sub i) and (N sub j) in the spanning tree. Summing over all n(2) pairs of nodes, the author has the total cost of communication of the spanning tree. (Modified author abstract)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1973
- Accession Number
- AD0771388
Entities
People
- T. C. Hu
Organizations
- University of Wisconsin–Madison