An improved approximation ratio to the partial-terminal steiner tree problem

Chia Wei Lee, Chao Wen Huang, Wen Hao Pi, Sun-Yuan Hsieh

研究成果: Article同行評審

2 引文 斯高帕斯(Scopus)

摘要

We consider a generalization of both the classic Steiner tree problem and the terminal Steiner tree problem. Given a complete graph G = (V,E) with a metric cost function c:E BBQ≥ and two proper subsets R V and R′ R , a partial-terminal Steiner tree is a Steiner tree which contains all vertices in it R such that all vertices in R ′ must be leaves. The partial-terminal Steiner tree problem is to find a partial-terminal Steiner tree of the minimum cost in G. The previously best-known approximation ratio of the problem is 2ρ , where ρ is the approximation ratio of the Steiner tree problem. In this paper, we improve the ratio from 2ρ to 2ρ-ρ3ρ-2-f , where f is a non-negative function whose value is between 0 and ρ-ρ over 3ρ-2.

原文English
文章編號6636895
頁(從 - 到)274-279
頁數6
期刊IEEE Transactions on Computers
64
發行號1
DOIs
出版狀態Published - 2015 一月 1

All Science Journal Classification (ASJC) codes

  • 軟體
  • 理論電腦科學
  • 硬體和架構
  • 計算機理論與數學

指紋

深入研究「An improved approximation ratio to the partial-terminal steiner tree problem」主題。共同形成了獨特的指紋。

引用此