TY - GEN
T1 - On the internal steiner tree problem
AU - Hsieh, Sun Yuan
AU - Gao, Huang Ming
AU - Yang, Shih Cheng
PY - 2007
Y1 - 2007
N2 - Given a complete graph G = (V,E) with a cost function c : E → ℝ+ and a vertex subset R ⊂ V, an internal Steiner tree is a Steiner tree which contains all vertices in R such that each vertex in R is restricted to be an internal vertex. The internal Steiner tree problem is to find an internal Steiner tree T whose total costs Σ (u,v)∈E(T)c(u;v) is minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present an approximation algorithm with approximation ratio 2ρ + 1 for the problem, where ρ is the best known approximation ratio for the Steiner tree problem.
AB - Given a complete graph G = (V,E) with a cost function c : E → ℝ+ and a vertex subset R ⊂ V, an internal Steiner tree is a Steiner tree which contains all vertices in R such that each vertex in R is restricted to be an internal vertex. The internal Steiner tree problem is to find an internal Steiner tree T whose total costs Σ (u,v)∈E(T)c(u;v) is minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present an approximation algorithm with approximation ratio 2ρ + 1 for the problem, where ρ is the best known approximation ratio for the Steiner tree problem.
UR - http://www.scopus.com/inward/record.url?scp=35449001935&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35449001935&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-72504-6_25
DO - 10.1007/978-3-540-72504-6_25
M3 - Conference contribution
AN - SCOPUS:35449001935
SN - 3540725032
SN - 9783540725039
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 274
EP - 283
BT - Theory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings
PB - Springer Verlag
T2 - 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007
Y2 - 22 May 2007 through 25 May 2007
ER -