(1+ρ)-Approximation for Selected-Internal Steiner Minimum Tree

摘要

Selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted complete graph G=(V, E)with weight function c, and two subsets R C R C V with |R-R |≥2, selected-internal Steiner minimuM tree problem is to find a Steiner minimum tree T of g spanning R such that any leaf of T does not belong to R. In this paper, suppose c is metric, we obtain a (1+ρ)-approximation algorithm for this problem, where ρ is the best-known approximation ratio for the Steiner minimum tree problem.