Approximating the selected-internal Steiner tree
In this paper, we consider a variant of the well-known Steiner tree problem. Given a complete graph G = (V, E) with a cost function c : E -> R+ and two subsets R and R' satisfying R' subset of R subset of V, a selected-internal Steiner tree is a Steiner tree which contains (or spans) all the vertices in R such that each vertex in R' cannot be a leaf. The selected-internal Steiner tree problem is to find a selected-internal Steiner tree with the minimum cost. In this paper, we present a 2 rho-approximation algorithm for the problem, where p is the best-known approximation ratio for the Steiner tree problem. (c) 2007 Elsevier B.V. All rights reserved.
steiner tree the selected-internal steiner tree problem design and analysis of algorithms approximation algorithms max snp-hard