Approximation algorithms for the k-source multicast tree construction problem

Given an undirected graph with nonnegative weights on its edges, a group of source nodes, and a group of destination nodes, we investigate the problem of constructing a multicast tree that minimizes the sum of distances from a destination node to all sources. This problem has been proven to be NP-complete. In this article, we show that there is a point c of the graph such that a shortest paths tree constructed from c is a 2-approximation to the problem, a significant improvement over the previous results, and we present an efficient approximation algorithm.