TY - JOUR
T1 - Approximating the selected-internal Steiner tree
AU - Hsieh, Sun Yuan
AU - Yang, Shih Cheng
N1 - Funding Information:
I An extended abstract of this paper appeared in Proceedings of 12th Annual International Computing and Combinatorics Conference (COCOON 2006), Lecture Notes in Computer Science 4112, pp. 449–458, 2006. This work was supported in part by the National Science Council under grants NSC 94-2213-E-006-073 and NSC 95-2221-E-006-076. ∗Corresponding author. E-mail address: [email protected] (S.-Y. Hsieh).
PY - 2007/8/22
Y1 - 2007/8/22
N2 - 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′ ⊂ R ⊆ 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 ρ-approximation algorithm for the problem, where ρ is the best-known approximation ratio for the Steiner tree problem.
AB - 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′ ⊂ R ⊆ 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 ρ-approximation algorithm for the problem, where ρ is the best-known approximation ratio for the Steiner tree problem.
UR - http://www.scopus.com/inward/record.url?scp=34547222050&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34547222050&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2007.05.035
DO - 10.1016/j.tcs.2007.05.035
M3 - Article
AN - SCOPUS:34547222050
SN - 0304-3975
VL - 381
SP - 288
EP - 291
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-3
ER -