(1+ρ)-Approzimation for Selected-Internal Steiner Minimum Tree

摘要：

Selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted complete graph G=(V, E)with weight function c, and two subsets R C R C V with |R-R |≥2, selected-internal Steiner minimuM tree problem is to find a Steiner minimum tree T of g spanning R such that any leaf of T does not belong to R. In this paper, suppose c is metric, we obtain a (1+ρ)-approximation algorithm for this problem, where ρ is the best-known approximation ratio for the Steiner minimum tree problem.

作者: Xianyue Li Yaochun Huang Feng Zou Donghyun Kim Weili Wu

作者单位: School of Mathematics and Statistics, Lanzhou University,Lanzhou,Gansu, 730000, P.R. China Department of Computer Science, University of Texas at Dallas,Richardson, TX 75080, USA Department of Computer Science, University of Texas at Dallas,Richardson,TX 75080, USA Department of Computer Science,University of Texas at Dallas,Richardson, TX 75080, USA

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 568-576

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）