On the internal steiner tree problem

Sun Yuan Hsieh; Huang Ming Gao; Shih Cheng Yang

doi:10.1007/978-3-540-72504-6_25

On the internal steiner tree problem

Sun Yuan Hsieh, Huang Ming Gao, Shih Cheng Yang

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

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
Publisher	Springer Verlag
Pages	274-283
Number of pages	10
ISBN (Print)	3540725032, 9783540725039
DOIs	https://doi.org/10.1007/978-3-540-72504-6_25
Publication status	Published - 2007
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/Territory	China
City	Shanghai
Period	07-05-22 → 07-05-25

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-72504-6_25

Cite this

Hsieh, S. Y., Gao, H. M., & Yang, S. C. (2007). On the internal steiner tree problem. In Theory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings (pp. 274-283). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4484 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-72504-6_25

@inproceedings{800bc013bc8e4f209149dcc63a7e151f,

title = "On the internal steiner tree problem",

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.",

author = "Hsieh, {Sun Yuan} and Gao, {Huang Ming} and Yang, {Shih Cheng}",

year = "2007",

doi = "10.1007/978-3-540-72504-6_25",

language = "English",

isbn = "3540725032",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "274--283",

booktitle = "Theory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings",

address = "Germany",

note = "4th International Conference on Theory and Applications of Models of Computation, TAMC 2007 ; Conference date: 22-05-2007 Through 25-05-2007",

}

Hsieh, SY, Gao, HM & Yang, SC 2007, On the internal steiner tree problem. in Theory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4484 LNCS, Springer Verlag, pp. 274-283, 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, Shanghai, China, 07-05-22. https://doi.org/10.1007/978-3-540-72504-6_25

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. Springer Verlag, 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

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 -

Hsieh SY, Gao HM, Yang SC. On the internal steiner tree problem. In Theory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings. Springer Verlag. 2007. p. 274-283. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-540-72504-6_25

On the internal steiner tree problem

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this