An O(n log n) average time algorithm for computing the shortest network under a given topology

CSpace

	An O(n log n) average time algorithm for computing the shortest network under a given topology
	Xue, G ; Du, DZ
	1999-04-01
发表期刊	ALGORITHMICA
ISSN	0178-4617
卷号	23 期号:4 页码:354-362
摘要	In 1992 F. K. Hwang and J. F. Weng published an O(n(2)) time algorithm for computing the shortest network under a given full Steiner topology interconnecting n fixed points in the Euclidean plane, The Hwang-Weng algorithm can be used to improve substantially existing algorithms for the Steiner minimum tree problem because it reduces the number of different Steiner topologies to be considered dramatically. In this paper we present an improved Hwang-Weng algorithm. While the worst-case time complexity of our algorithm is still O (n(2)), its average time complexity over all the full Steiner topologies interconnecting n fixed points is O (n log n).
关键词	analysis of algorithms Steiner minimum trees shortest network under a given topology
语种	英语
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Software Engineering ; Mathematics, Applied
WOS记录号	WOS:000078197000005
出版者	SPRINGER VERLAG
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/14169
专题	中国科学院数学与系统科学研究院
通讯作者	Xue, G
作者单位	1.Univ Vermont, Dept Comp Sci, Burlington, VT 05405 USA 2.Univ Minnesota, Dept Comp Sci, Minneapolis, MN 55455 USA 3.Chinese Acad Sci, Inst Appl Math, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Xue, G,Du, DZ. An O(n log n) average time algorithm for computing the shortest network under a given topology[J]. ALGORITHMICA,1999,23(4):354-362.
APA	Xue, G,&Du, DZ.(1999).An O(n log n) average time algorithm for computing the shortest network under a given topology.ALGORITHMICA,23(4),354-362.
MLA	Xue, G,et al."An O(n log n) average time algorithm for computing the shortest network under a given topology".ALGORITHMICA 23.4(1999):354-362.