Constrained Optimum Communication Trees and Sensitivity Analysis

Abstract

Consider n cities with specified communication requirements between all pairs of cities. An optimum communication tree has the property that among all the spanning trees connecting the n cities, the sum of its costs of communication for the $n(n - 1)/2$ pairs of cities is minimum. The cost of communication between a pair of nodes, with respect to a spanning tree, is the product of the communication requirement and the length of the path between the two cities. We construct constrained optimum communication trees when (i) certain specified cities are required to be the outer nodes of the communication tree, and when (ii) it is required that certain pairs of cities be connected directly in the communication tree. We further analyse changes in the structure of an optimum communication tree when the communication requirement between a pair of cities is subject to changes. We show that for the whole range $[0,\infty )$, of the communication requirement, there exist at most $(n - 1)$ optimum communication trees and we construct all of them in $O(n^4 )$ computational effort.