MAX-SNP hardness and approximation of selected-internal steiner trees

Sun Yuan Hsieh, Shih Cheng Yang

研究成果: Conference contribution

摘要

In this paper, we consider an interesting variant of the well-known Steiner tree problem: Given a complete graph G = (V, E) with a cost function c : E → R+ and two subsets R and R′ satisfying R′ ⊂ R ⊆ V, a selected-internal Steiner tree is a Steiner tree which contains (or spans) all the vertices in R such that each vertex in R′ cannot be a leaf. The selected-internal Steiner tree problem is to find a selected-internal Steiner tree with the minimum cost. In this paper, we show that the problem is MAX SNP-hard even when the costs of all edges in the input graph are restricted to either 1 or 2. We also present an approximation algorithm for the problem.

原文English
主出版物標題Computing and Combinatorics - 12th Annual International Conference, COCOON 2006, Proceedings
發行者Springer Verlag
頁面449-458
頁數10
ISBN(列印)3540369252, 9783540369257
DOIs
出版狀態Published - 2006 1月 1
事件12th Annual International Conference on Computing and Combinatorics, COCOON 2006 - Taipei, Taiwan
持續時間: 2006 8月 152006 8月 18

出版系列

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

Other

Other12th Annual International Conference on Computing and Combinatorics, COCOON 2006
國家/地區Taiwan
城市Taipei
期間06-08-1506-08-18

All Science Journal Classification (ASJC) codes

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

指紋

深入研究「MAX-SNP hardness and approximation of selected-internal steiner trees」主題。共同形成了獨特的指紋。

引用此