Premium
Approximation algorithms for the k‐source multicast tree construction problem
Author(s) -
Fragopoulou Paraskevi
Publication year - 2006
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20107
Subject(s) - multicast , steiner tree problem , computer science , gomory–hu tree , tree (set theory) , approximation algorithm , graph , combinatorics , k ary tree , node (physics) , mathematics , theoretical computer science , discrete mathematics , algorithm , tree structure , distributed computing , binary tree , structural engineering , engineering
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. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(3), 178–183 2006