کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4608688 | 1338372 | 2013 | 17 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The internal Steiner tree problem: Hardness and approximations The internal Steiner tree problem: Hardness and approximations](/preview/png/4608688.png)
Given a graph G=(V,E)G=(V,E) with a cost function c:E→R+c:E→R+ and a vertex subset R⊂VR⊂V, an internal Steiner tree is a Steiner tree that contains all the vertices in RR, and such that each vertex in RR must be an internal vertex. The internal Steiner tree problem involves finding an internal Steiner tree TT whose total cost ∑(u,v)∈E(T)c(u,v)∑(u,v)∈E(T)c(u,v) is the minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present a (2ρ+1)(2ρ+1)-approximation algorithm for solving the problem on complete graphs, where ρρ is an approximation ratio for the Steiner tree problem. Currently, the best-known ρρ is ln4+ϵ<1.39ln4+ϵ<1.39. Moreover, for the case where the cost of each edge is restricted to being either 1 or 2, we present a 97-approximation algorithm for the problem.
Journal: Journal of Complexity - Volume 29, Issue 1, February 2013, Pages 27–43