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

CSpace

	A PROOF OF THE GILBERT-POLLAK CONJECTURE ON THE STEINER RATIO
	DU, DZ ; HWANG, FK
	1992
发表期刊	ALGORITHMICA
ISSN	0178-4617
卷号	7 期号:2-3 页码:121-135
摘要	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.
关键词	STEINER TREES SPANNING TREES STEINER RATIO CONVEXITY HEXAGONAL TREES
语种	英语
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Software Engineering ; Mathematics, Applied
WOS记录号	WOS:A1992HA31400002
出版者	SPRINGER VERLAG
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/28206
专题	中国科学院数学与系统科学研究院
通讯作者	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.