Given a complete graph G = (V, E) with a metric cost function c: E -> ℝ+ and two proper subsets R ⊂ V and R' ⊆ R, a Steiner tree is a connected and acyclic subgraph of G which contains all vertices in R. We consider a generalization of the classic Steiner tree problem and the terminal Steiner tree problem, a partial-terminal Steiner tree is a Steiner tree which contains all vertices in R such that all vertices in R' must be leaves. The partial-terminal Steiner tree problem is to find a partial-terminal Steiner tree of the minimum cost in G.
The application of the partial-terminal Steiner tree problem on IC design.
The previously best-known approximation ratio of the problem is 2ρ, where ρ is the approximation ratio of the Steiner tree problem. In this paper, we improve the approximation ratio from 2ρ to 2ρ-[(ρ)/(3ρ-2)]-f, where f is a non-negative function whose value is between 0 and ρ-[(ρ)/(3ρ-2)] .
The approximation ratios of the proposed algorithm and previously best-known algorithm.
