Abstract
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.
| Original language | English |
|---|---|
| Title of host publication | Theory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings |
| Pages | 274-283 |
| Number of pages | 10 |
| Publication status | Published - 2007 Oct 29 |
| Event | 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007 - Shanghai, China Duration: 2007 May 22 → 2007 May 25 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 4484 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Other
| Other | 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007 |
|---|---|
| Country | China |
| City | Shanghai |
| Period | 07-05-22 → 07-05-25 |
Fingerprint
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)
Cite this
}
On the internal steiner tree problem. / Hsieh, Sun-Yuan; Gao, Huang Ming; Yang, Shih Cheng.
Theory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings. 2007. p. 274-283 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4484 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
TY - GEN
T1 - On the internal steiner tree problem
AU - Hsieh, Sun-Yuan
AU - Gao, Huang Ming
AU - Yang, Shih Cheng
PY - 2007/10/29
Y1 - 2007/10/29
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
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
ER -