The k-Steiner ratio in the rectilinear plane

	The k-Steiner ratio in the rectilinear plane
	Borchers, A ; Du, DZ ; Gao, B ; Wan, PJ
刊名	JOURNAL OF ALGORITHMS
	1998-10-01
卷号	29 期号:1 页码:1-17
ISSN号	0196-6774
英文摘要	A Steiner minimum tree (SMT) in the rectilinear plane is the shortest length tree interconnecting a set of points, called the regular points, possibly using additional vertices. A k-size Steiner minimum tree (kSMT) is one that can be split into components where all regular points are leaves and all components have at most k leaves. The k-Steiner ratio in the rectilinear plane, Pk, is the infimum of the ratios SMT/kSMT over all finite sets of regular points. The k-Steiner ratio is used to determine the performance ratio of several recent polynomial-time approximations for Steiner minimum trees. Previously it was known that in the rectilinear plane, rho(2) = 2/3, rho(3) = 4/5, and (2k - 2)/(2k - 1.) less than or equal to rho(k)(L,(1)) less than or equal to (2k - 1)/(2k) for k greater than or equal to 4. In 1991, P. Berman and V. Ramaiyer conjectured that in fact rho(k) = (2k-1)/(2k) for k greater than or equal to 4. In this paper we prove their conjecture. (C) 1998 Academic Press.
WOS研究方向	Computer Science ; Mathematics ; Science & Technology - Other Topics
语种	英语
出版者	ACADEMIC PRESS INC
WOS记录号	WOS:000076061100001
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/13436]
专题	中国科学院数学与系统科学研究院
通讯作者	Borchers, A
作者单位	1.Univ Minnesota, Dept Comp Sci, Minneapolis, MN 55455 USA 2.Chinese Acad Sci, Inst Appl Math, Beijing, Peoples R China 3.Lattice Semicond Corp, Milpitas, CA 95125 USA 4.IIT, Dept Appl Math & Comp Sci, Chicago, IL 60616 USA
推荐引用方式 GB/T 7714	Borchers, A,Du, DZ,Gao, B,et al. The k-Steiner ratio in the rectilinear plane[J]. JOURNAL OF ALGORITHMS,1998,29(1):1-17.
APA	Borchers, A,Du, DZ,Gao, B,&Wan, PJ.(1998).The k-Steiner ratio in the rectilinear plane.JOURNAL OF ALGORITHMS,29(1),1-17.
MLA	Borchers, A,et al."The k-Steiner ratio in the rectilinear plane".JOURNAL OF ALGORITHMS 29.1(1998):1-17.