Optimum Communication Spanning Trees

The cost of communication for a pair of nodes is multiplied by the sum of the distances of arcs which form the unique path connecting N_i and N_j in the spanning tree.

Abstract

Given a set of nodes $N_i (i = 1,2, \cdots ,n)$ which may represent cities and a set of requirements $r_{ij} $ which may represent the number of telephone calls between $N_i $ and $N_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_{ij} $ multiplied by the sum of the distances of arcs which form the unique path connecting $N_i $ and $N_j $ in the spanning tree. Summing over all $\begin{pmatrix} n \\ 2 \ \end{pmatrix}$ pairs of nodes, we have the total cost of communication of the spanning tree. Note that the problem is different from the minimum spanning tree problem solved by Kruskal and Prim.