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 -