Volume 31 Issue 10 - November 15, 2019 PDF
Counter
An improved approximation ratio to the partial-terminal Steiner tree problem
Chia-Wei Lee, Chao-Wen Huang, Wen-Hao Pi, and Sun-Yuan Hsieh*
Department of Computer Science and Information Engineering, National Cheng Kung University
 
Font Enlarge
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 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.
< Previous
Next >
Copyright National Cheng Kung University