Wire segmenting for buffer insertion based on RSTP-MSP
文献类型：期刊论文
| 作者 | Lu, B; Gu, J; Hu, XD ; Shragowitz, E
|
| 刊名 | THEORETICAL COMPUTER SCIENCE
 |
| 出版日期 | 2001-07-06 |
| 卷号 | 262期号:1-2页码:257-267 |
| 关键词 | VLSI wire segment buffer insertion rectilinear Steiner tree minimum spanning tree approximation algorithm |
| ISSN号 | 0304-3975 |
| 英文摘要 | 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. |
| WOS研究方向 | Computer Science |
| 语种 | 英语 |
| WOS记录号 | WOS:000169594100015 |
| 出版者 | ELSEVIER SCIENCE BV |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/15913]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | 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. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。