The problem of finding an optimum communication tree is as follows: given a set of n cities with specified communication requirements between all cities, find the spanning tree connecting the n cities such that the sum of the costs for communication for the n(n-1)/2 pairs of cities is minimal. In other words, the problem is to minimize over a spanning tree T: :9I (the number of links in the path from i to j in T) where r_{ij:E is the communication requirement between node i and node j and where we have taken the distance between every pair of nodes to be unity.}

Hu solved the above problem in [1]. The present authors solve the problem with the following two constraints:

:.F

• (1) Certain specified cities are required to be outer nodes of the communication tree. (The algorithm is given in Pidgin ALGOL and has time complexity O(n²).

• (2) Certain pairs of cities are required to be directly connected in the communication tree.

These generalizations of the optimum communication tree problem have applications to several actual situations which are listed in the paper.

The last part of the paper analyses the changes in the structure of the optimum communication tree when the communication requirement between a pair of cities is subject to change. It is shown that for the whole range (O,:9I of the communication requirement, there exist at most (n-1) optimum communicatio trees. An algorithm is given to construct all of these in O(n₄) computational effort.