Steiner tree problem with minimum number of Steiner points and bounded edge-length

CSpace

	Steiner tree problem with minimum number of Steiner points and bounded edge-length
	Lin, GH ; Xue, GL
	1999-01-29
发表期刊	INFORMATION PROCESSING LETTERS
ISSN	0020-0190
卷号	69 期号:2 页码:53-57
摘要	In this paper, we study the Steiner tree problem with minimum number of Steiner points and bounded edge-length (STP-MSPBEL), which asks for a tree interconnecting a given set of n terminal points and a minimum number of Steiner points such that the Euclidean length of each edge is no more than a given positive constant. This problem has applications in VLSI design, WDM optimal networks and wireless communications. We prove that this problem is NP-complete and present a polynomial time approximation algorithm whose worst-case performance ratio is 5. (C) 1999 Elsevier Science B.V. All rights reserved.
关键词	algorithms approximation algorithms Steiner minimum trees VLSI design WDM optimal networks wireless communications
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems
WOS记录号	WOS:000078662100001
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/14445
专题	中国科学院数学与系统科学研究院
通讯作者	Xue, GL
作者单位	1.Univ Vermont, Dept Comp Sci, Burlington, VT 05405 USA 2.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Lin, GH,Xue, GL. Steiner tree problem with minimum number of Steiner points and bounded edge-length[J]. INFORMATION PROCESSING LETTERS,1999,69(2):53-57.
APA	Lin, GH,&Xue, GL.(1999).Steiner tree problem with minimum number of Steiner points and bounded edge-length.INFORMATION PROCESSING LETTERS,69(2),53-57.
MLA	Lin, GH,et al."Steiner tree problem with minimum number of Steiner points and bounded edge-length".INFORMATION PROCESSING LETTERS 69.2(1999):53-57.