Algorithms for the optimum communication spanning tree problem

摘要

Optimum Communication Spanning Tree Problem is a special case of the Network Design Problem. In this problem given a graph, a set of requirements r_(ij) and a set of distances d_(ij) 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 r_(ij) 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 (1974) 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 d_(ij) equal to the smallest d_(ij). For arcs (i, j) which are part of this cut-tree the corresponding d_(ij) value is increased to obtain a near optimal communication spanning tree in pseudo-polynomial time. In case the distances d_(ij) satisfy a generalised triangle inequality the second algorithm in the paper constructs a near optimum tree in polynomial time by parametrising on the r_(ij).