An improved approximation algorithm for capacitated multicast routings in networks

Abstract: Let be a connected graph such that each edge is weighted by nonnegative real . Let be a vertex designated as a source, be a positive integer, and be a set of terminals. The capacitated multicast tree routing problem (CMTR) asks to find a partition of and a set of trees of such that consists of at most terminals and each spans . The objective is to minimize , where denotes the sum of weights of all edges in . In this paper, we propose a -approximation algorithm to the CMTR, where is the best achievable approximation ratio for the Steiner tree problem. [Copyright &y& Elsevier]