On minimum-weight k-edge connected Steiner networks on metric spaces

CSpace > 应用数学研究所

	On minimum-weight k-edge connected Steiner networks on metric spaces
	Hsu, DF ; Hu, XD; Lin, GH
	2000
发表期刊	GRAPHS AND COMBINATORICS
ISSN	0911-0119
卷号	16 期号:3 页码:275-284
摘要	For a given set of points P in a metric space, let w(k)(P) denote the weight of minimum-weight k-edge connected Steiner network on P divided by the weight of minimum-weight k-edge connected spanning network on P, and let r(k) = inf{w(k)(P)\P}. We show in this paper that for any P, w(k)(P) greater than or equal to 1 - 1/k+2, for even k greater than or equal to 2 and w(k)(P) greater than or equal to 1 - 1/k+1, for odd k greater than or equal to 3. In particular, we prove that for any P in the Euclidean plane, w(4)(P) and w(5)(P) are greater than or equal to root3/2, and r(5) less than or equal to 1/8 (7 + 1/32 + root3/2 - root 129/128); For any P in the rectilinear plane r(k) less than or equal to 1 - 1/3k+1, for odd k greater than or equal to 5. In addition, we prove that there exists an O(\P\(3))-time approximation algorithm for constructing a minimum-weight k-edge connected Steiner network which has approximation ratio of 3/2 for even k and (3/2 + 1/2k) for odd k.
语种	英语
WOS研究方向	Mathematics
WOS类目	Mathematics
WOS记录号	WOS:000168577600003
出版者	SPRINGER-VERLAG
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/15232
专题	应用数学研究所
通讯作者	Hsu, DF
作者单位	1.Fordham Univ, Dept Comp & Informat Sci, Bronx, NY 10458 USA 2.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Hsu, DF,Hu, XD,Lin, GH. On minimum-weight k-edge connected Steiner networks on metric spaces[J]. GRAPHS AND COMBINATORICS,2000,16(3):275-284.
APA	Hsu, DF,Hu, XD,&Lin, GH.(2000).On minimum-weight k-edge connected Steiner networks on metric spaces.GRAPHS AND COMBINATORICS,16(3),275-284.
MLA	Hsu, DF,et al."On minimum-weight k-edge connected Steiner networks on metric spaces".GRAPHS AND COMBINATORICS 16.3(2000):275-284.