An efficient low-degree RMST algorithm for VLSI/ULSI physical design

CSpace > 应用数学研究所

	An efficient low-degree RMST algorithm for VLSI/ULSI physical design
	Wang, Y ; Hong, XL ; Jing, T ; Yang, Y ; Hu, XD; Yan, GY
	2004
发表期刊	INTEGRATED CIRCUIT AND SYSTEM DESIGN
ISSN	0302-9743
卷号	3254 页码:442-452
摘要	Motivated by very/ultra large scale integrated circuit (VLSI/ULSI) physical design applications, we study the construction of rectilinear minimum spanning tree (RMST) with its maximum vertex degree as the constraint. Given a collection of n points in the plane, we firstly construct a graph named the bounded-degree neighborhood graph (BNG). Based on this framework, we propose an O(n log n) algorithm to construct a 4-BDRMST (RMST with maximum vertex degree less than or equal to 4). This is the first 4-BDRMST algorithm with such a complexity, and experimental results show that the algorithm is significantly faster than the existing 4-BDRMST algorithms.
语种	英语
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic
WOS记录号	WOS:000224072900046
出版者	SPRINGER-VERLAG BERLIN
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/783
专题	应用数学研究所
通讯作者	Wang, Y
作者单位	1.Tsing Hua Univ, Dept Comp Sci & Technol, Beijing 100084, Peoples R China 2.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Wang, Y,Hong, XL,Jing, T,et al. An efficient low-degree RMST algorithm for VLSI/ULSI physical design[J]. INTEGRATED CIRCUIT AND SYSTEM DESIGN,2004,3254:442-452.
APA	Wang, Y,Hong, XL,Jing, T,Yang, Y,Hu, XD,&Yan, GY.(2004).An efficient low-degree RMST algorithm for VLSI/ULSI physical design.INTEGRATED CIRCUIT AND SYSTEM DESIGN,3254,442-452.
MLA	Wang, Y,et al."An efficient low-degree RMST algorithm for VLSI/ULSI physical design".INTEGRATED CIRCUIT AND SYSTEM DESIGN 3254(2004):442-452.