Approximating the selected-internal Steiner tree

Sun Yuan Hsieh, Shih Cheng Yang

研究成果: Article同行評審

10 引文 斯高帕斯(Scopus)

摘要

In this paper, we consider a 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 present a 2 ρ-approximation algorithm for the problem, where ρ is the best-known approximation ratio for the Steiner tree problem.

原文English
頁(從 - 到)288-291
頁數4
期刊Theoretical Computer Science
381
發行號1-3
DOIs
出版狀態Published - 2007 八月 22

All Science Journal Classification (ASJC) codes

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

指紋

深入研究「Approximating the selected-internal Steiner tree」主題。共同形成了獨特的指紋。

引用此