A Better Constant-Factor Approximation for Selected-Internal Steiner Minimum Tree

摘要

The 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' is contained in R is contained in V with |R - R'| ≥ 2, selected-internal Steiner minimum tree problem is to find a minimum subtree T of G interconnecting 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 p is the best-known approximation ratio for the Steiner minimum tree problem.