An Approximation Algorithm for Constructing Multicast Trees with Degree-Dependent Node Costs

This paper studies the problem of constructing a minimum-cost multicast tree (or Seiner tree) in which each node is associated with a cost that is dependent on the degree of the node on the multicast tree. The cost of a node may depend on its degree on the multicast tree due to a number of reasons. For example, a node may need to perform various processing for sending messages to each of its neighbors on the multicast tree. Thus, the overhead for processing the messages increases as the number of neighbors increases. This paper devises a novel technique to deal with the degree-dependent node costs and applies the technique to develop an approximation algorithm for the problem. The bound on the cost of the multicast tree constructed by the proposed approximation algorithm is derived.