On shortest k-edge-connected Steiner networks in metric spaces

CSpace > 应用数学研究所

	On shortest k-edge-connected Steiner networks in metric spaces
	Du, XF ; Hu, XD; Jia, XH
	2000-03-01
发表期刊	JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN	1382-6905
卷号	4 期号:1 页码:99-107
摘要	Given a set of points P in a metric space, let l(k)(P) denote the ratio of lengths between the shortest k-edge-connected Steiner network and the shortest k-edge-connected spanning network on P, and let r(k) = inf{l(k)(P) \ P} for k greater than or equal to 1. In this paper, we show that in any metric space, r(k) greater than or equal to 3/4 for k greater than or equal to 2, and there exists a polynomial-time alpha-approximation for the shortest k-edge-connected Steiner network, where alpha = 2 for even k and alpha = 2 + 4/(3k) for odd k. In the Euclidean plane, r(k) greater than or equal to root 3/2, r(3) less than or equal to (root 3+2)/4 and r(4) less than or equal to (7+3 root 3)/(9+2 root 3).
关键词	k-edge-connectivity spanning networks Steiner networks Steiner ratio
语种	英语
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Interdisciplinary Applications ; Mathematics, Applied
WOS记录号	WOS:000085622400005
出版者	KLUWER ACADEMIC PUBL
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/15359
专题	应用数学研究所
通讯作者	Du, XF
作者单位	1.Univ Qiqihaer, Dept Math, Heilongjiang, Peoples R China 2.Chinese Acad Sci, Inst Appl Math, Beijing, Peoples R China 3.City Univ Hong Kong, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China
推荐引用方式 GB/T 7714	Du, XF,Hu, XD,Jia, XH. On shortest k-edge-connected Steiner networks in metric spaces[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,2000,4(1):99-107.
APA	Du, XF,Hu, XD,&Jia, XH.(2000).On shortest k-edge-connected Steiner networks in metric spaces.JOURNAL OF COMBINATORIAL OPTIMIZATION,4(1),99-107.
MLA	Du, XF,et al."On shortest k-edge-connected Steiner networks in metric spaces".JOURNAL OF COMBINATORIAL OPTIMIZATION 4.1(2000):99-107.