Wire segmenting for buffer insertion based on RSTP-MSP

CSpace > 应用数学研究所

	Wire segmenting for buffer insertion based on RSTP-MSP
	Lu, B ; Gu, J ; Hu, XD; Shragowitz, E
	2001-07-06
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	262 期号:1-2 页码:257-267
摘要	This paper presents an approximation algorithm for simultaneously constructing a rectilinear Steiner tree and buffer insertion points into the tree. The objective of the algorithm is to divide each wire into multiple smaller segments and minimize the number of the buffer insertion points (Steiner points) which are only located at the end of each segment. We show that (a) the Steiner ratio is 1/3, that is, the rectilinear minimum spanning tree yields a polynomial-time approximation with a performance ratio exactly 3; (b) there exists a polynomial-time approximation with a performance ratio 2. (C) 2001 Elsevier Science B.V. All rights reserved.
关键词	VLSI wire segment buffer insertion rectilinear Steiner tree minimum spanning tree approximation algorithm
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000169594100015
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/15914
专题	应用数学研究所
通讯作者	Lu, B
作者单位	1.Univ Minnesota, Dept Comp Sci, Minneapolis, MN 55455 USA 2.Hong Kong Univ Sci & Technol, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China 3.Chinese Acad Sci, Inst Appl Math, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Lu, B,Gu, J,Hu, XD,et al. Wire segmenting for buffer insertion based on RSTP-MSP[J]. THEORETICAL COMPUTER SCIENCE,2001,262(1-2):257-267.
APA	Lu, B,Gu, J,Hu, XD,&Shragowitz, E.(2001).Wire segmenting for buffer insertion based on RSTP-MSP.THEORETICAL COMPUTER SCIENCE,262(1-2),257-267.
MLA	Lu, B,et al."Wire segmenting for buffer insertion based on RSTP-MSP".THEORETICAL COMPUTER SCIENCE 262.1-2(2001):257-267.