On the internal steiner tree problem

Sun Yuan Hsieh, Huang Ming Gao, Shih Cheng Yang

研究成果: Conference contribution

3 引文 斯高帕斯(Scopus)

摘要

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.

原文English
主出版物標題Theory and Applications of Models of Computation - 4th International Conference, TAMC 2007, Proceedings
發行者Springer Verlag
頁面274-283
頁數10
ISBN(列印)3540725032, 9783540725039
DOIs
出版狀態Published - 2007
事件4th International Conference on Theory and Applications of Models of Computation, TAMC 2007 - Shanghai, China
持續時間: 2007 5月 222007 5月 25

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
4484 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

Other

Other4th International Conference on Theory and Applications of Models of Computation, TAMC 2007
國家/地區China
城市Shanghai
期間07-05-2207-05-25

All Science Journal Classification (ASJC) codes

  • 理論電腦科學
  • 電腦科學(全部)

指紋

深入研究「On the internal steiner tree problem」主題。共同形成了獨特的指紋。

引用此