The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points

CSpace

	The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points
	Du, DZ ; Wang, LS ; Xu, BA
	2001
发表期刊	COMPUTING AND COMBINATORICS
ISSN	0302-9743
卷号	2108 页码:509-518
摘要	We study variations of Steiner tree problem. Let P = {p(1), p(2), .... p(n)} be a set of n terminals in the Euclidean plane. For a positive integer k, the bottleneck Steiner tree problem (BSTP for short) is to find a Steiner tree with at most k Steiner points such that the length of the longest edges in the tree is minimized. For a positive constant R, the Steiner tree problem with minimum number of Steiner points (STP - MSP for short) asks for a Steiner tree such that each edge in the tree has length at most R and the number of Steiner points is minimized. In this paper, we give (1) a ratio-root3 + epsilon approximation algorithm for BSTP, where c is an arbitrary positive number; (2) a ratio-3 approximation algorithm for STP-MSP with running time O(n(3)); (3) a ratio-E approximation algorithm for STP-MSP.
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000179960000057
出版者	SPRINGER-VERLAG BERLIN
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/15962
专题	中国科学院数学与系统科学研究院
通讯作者	Du, DZ
作者单位	1.Univ Minnesota, Dept Comp Sci & Engn, Minneapolis, MN 55455 USA 2.City Univ Hong Kong, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China 3.Chinese Acad Sci, Acad Math & Syst Sci, Inst Syst Sci, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Du, DZ,Wang, LS,Xu, BA. The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points[J]. COMPUTING AND COMBINATORICS,2001,2108:509-518.
APA	Du, DZ,Wang, LS,&Xu, BA.(2001).The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points.COMPUTING AND COMBINATORICS,2108,509-518.
MLA	Du, DZ,et al."The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points".COMPUTING AND COMBINATORICS 2108(2001):509-518.