ON GREEDY HEURISTICS FOR STEINER MINIMUM TREES

CSpace

	ON GREEDY HEURISTICS FOR STEINER MINIMUM TREES
	DU, DZ
	1995-04-01
发表期刊	ALGORITHMICA
ISSN	0178-4617
卷号	13 期号:4 页码:381-386
摘要	We disprove a conjecture of Shor and Smith on a greedy heuristic for the Steiner minimum tree by showing that the length ratio between the Steiner minimum tree and the greedy tree constructed by their method for the same set of points can be arbitrarily close to root 3/2. We also propose a new conjecture.
关键词	STEINER TREES GREED HEURISTIC
语种	英语
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Software Engineering ; Mathematics, Applied
WOS记录号	WOS:A1995QK30600004
出版者	SPRINGER VERLAG
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/27455
专题	中国科学院数学与系统科学研究院
通讯作者	DU, DZ
作者单位	CHINESE ACAD SCI,INST APPL MATH,BEIJING 100080,PEOPLES R CHINA
推荐引用方式 GB/T 7714	DU, DZ. ON GREEDY HEURISTICS FOR STEINER MINIMUM TREES[J]. ALGORITHMICA,1995,13(4):381-386.
APA	DU, DZ.(1995).ON GREEDY HEURISTICS FOR STEINER MINIMUM TREES.ALGORITHMICA,13(4),381-386.
MLA	DU, DZ."ON GREEDY HEURISTICS FOR STEINER MINIMUM TREES".ALGORITHMICA 13.4(1995):381-386.