TY - JOUR

T1 - An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2

AU - Wei, Chia Chen

AU - Hsieh, Sun Yuan

AU - Lee, Chia Wei

AU - Peng, Sheng Lung

N1 - Funding Information:
This work was supported in part by National Science Council Taiwan under grant 101-2221-E-006-276-MY2 .
Publisher Copyright:
© 2015 Elsevier B.V. All rights reserved.

PY - 2015/11

Y1 - 2015/11

N2 - Given a complete graph G=(V,E) with a metric cost function c:E→R+ and two vertex subsets R⊂V and R′⊆R, a partial-terminal Steiner tree is a Steiner tree which contains all the vertices in R such that all the vertices in R′ are leaves. The partial-terminal Steiner tree problem (PTSTP) is to find a partial-terminal Steiner tree with the minimum cost. The problem has been shown to be NP-hard and MAX SNP-hard, even when the edge costs are restricted in {1,2}, namely, the (1,2)-partial-terminal Steiner tree problem (PTSTP(1,2)). In this paper, we consider PTSTP(1,2). The previous best-known approximation ratio of PTSTP(1,2) was at most 2514. In this paper, we propose a polynomial-time approximation algorithm that improves the approximation ratio from 2514 to 53.

AB - Given a complete graph G=(V,E) with a metric cost function c:E→R+ and two vertex subsets R⊂V and R′⊆R, a partial-terminal Steiner tree is a Steiner tree which contains all the vertices in R such that all the vertices in R′ are leaves. The partial-terminal Steiner tree problem (PTSTP) is to find a partial-terminal Steiner tree with the minimum cost. The problem has been shown to be NP-hard and MAX SNP-hard, even when the edge costs are restricted in {1,2}, namely, the (1,2)-partial-terminal Steiner tree problem (PTSTP(1,2)). In this paper, we consider PTSTP(1,2). The previous best-known approximation ratio of PTSTP(1,2) was at most 2514. In this paper, we propose a polynomial-time approximation algorithm that improves the approximation ratio from 2514 to 53.

UR - http://www.scopus.com/inward/record.url?scp=84947715532&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947715532&partnerID=8YFLogxK

U2 - 10.1016/j.jda.2015.10.003

DO - 10.1016/j.jda.2015.10.003

M3 - Article

AN - SCOPUS:84947715532

VL - 35

SP - 62

EP - 71

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

SN - 1570-8667

ER -