TY - GEN
T1 - On the partial-terminal steiner tree problem
AU - Hsieh, Sun-Yuan
AU - Pi, Wen Hao
PY - 2008/8/15
Y1 - 2008/8/15
N2 - Given a complete graph G = (V, E) with a length (or cost) function c: E → ℚ≥ and two proper subsets R ⊂ V and R′ ⊆ R, 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 length in G. 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 ratio from 2ρ to 2ρ - ρ/3ρ-2 - ε where ε is some non-negative number.
AB - Given a complete graph G = (V, E) with a length (or cost) function c: E → ℚ≥ and two proper subsets R ⊂ V and R′ ⊆ R, 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 length in G. 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 ratio from 2ρ to 2ρ - ρ/3ρ-2 - ε where ε is some non-negative number.
UR - http://www.scopus.com/inward/record.url?scp=49149130270&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=49149130270&partnerID=8YFLogxK
U2 - 10.1109/I-SPAN.2008.11
DO - 10.1109/I-SPAN.2008.11
M3 - Conference contribution
AN - SCOPUS:49149130270
SN - 9780769531250
T3 - Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN
SP - 173
EP - 177
BT - Proceedings - 9th International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN 2008
T2 - 9th International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN 2008
Y2 - 7 May 2008 through 9 May 2008
ER -