A PROOF OF THE GILBERT-POLLAK CONJECTURE ON THE STEINER RATIO

	A PROOF OF THE GILBERT-POLLAK CONJECTURE ON THE STEINER RATIO
	DU, DZ ; HWANG, FK
刊名	ALGORITHMICA
	1992
卷号	7 期号:2-3 页码:121-135
关键词	STEINER TREES SPANNING TREES STEINER RATIO CONVEXITY HEXAGONAL TREES
ISSN号	0178-4617
英文摘要	Let P be a set of n points on the euclidean plane. Let L(s)(P) and L(m)(P) denote the lengths of the Steiner minimum tree and the minimum spanning tree on P, respectively. In 1968, Gilbert and Pollak conjectured that for any P, L(s)(P) greater-than-or-equal-to (square-root 3/2)L(m)(P). We provide a proof for their conjecture in this paper.
WOS研究方向	Computer Science ; Mathematics
语种	英语
出版者	SPRINGER VERLAG
WOS记录号	WOS:A1992HA31400002
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/28205]
专题	中国科学院数学与系统科学研究院
通讯作者	DU, DZ
作者单位	1.CHINESE ACAD SCI,INST APPL MATH,BEIJING,PEOPLES R CHINA 2.AT&T BELL LABS,MURRAY HILL,NJ 07974
推荐引用方式 GB/T 7714	DU, DZ,HWANG, FK. A PROOF OF THE GILBERT-POLLAK CONJECTURE ON THE STEINER RATIO[J]. ALGORITHMICA,1992,7(2-3):121-135.
APA	DU, DZ,&HWANG, FK.(1992).A PROOF OF THE GILBERT-POLLAK CONJECTURE ON THE STEINER RATIO.ALGORITHMICA,7(2-3),121-135.
MLA	DU, DZ,et al."A PROOF OF THE GILBERT-POLLAK CONJECTURE ON THE STEINER RATIO".ALGORITHMICA 7.2-3(1992):121-135.