Optimum Communication Spanning Tree Problem is a special case of the Network Design Problem. In this problem given a graph, a set of requirements rij and a set of distances dij for all pair of nodes (i,j), the cost of communication for a pair of nodes (i,j), with respect to a spanning tree T is defined as rij times the length of the unique path in T, that connects nodes i and j. Total cost of communication for a spanning tree is the sum of costs for all pairs of nodes of G. The problem is to construct a spanning tree for which the total cost of communication is the smallest among all the spanning trees of G. The problem is known to be NP-hard. Hu solved two special cases of the problem in polynomial time. In this paper, using Hu's result the first algorithm begins with a cut-tree by keeping all dij equal to the smallest dij. For arcs (i,j) which are part of this cut-tree the corresponding dij value is increased to obtain a near optimal communication spanning tree in pseudo-polynomial time. In case the distances dij satisfy a generalised triangle inequality the second algorithm in the paper constructs a near optimum tree in polynomial time by parametrising on the rij.
