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 -