An Efficient Low-Degree RMST Algorithm for VLSI/ULSI Physical Design
An Efficient Low-Degree RMST Algorithm for VLSI/ULSI Physical Design
复制标题
一种用于 VLSI/ULSI 物理设计的高效低度 RMST 算法
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
G. Yan
中科院分区：
文献类型：
--
作者：
Yin Wang;Xianlong Hong;Tong Jing;Yang Yang;Xiaodong Hu;G. Yan
由非常大的大规模集成电路（VLSI/ULSI）物理设计应用，我们研究了直线最小跨越树（RMST）的构建，其最大顶点程度是约束。给定平面中n个点的集合，我们首先构造了一个名为“边界邻域图”（BNG）的图。基于此框架，我们提出了一个O（n log n）算法来构建4-bdrmst（具有最大顶点度的RMST（4）。这是具有如此复杂性的第一个4-BDRMST算法，实验结果表明，该算法表明，算法的速度明显快于现有的4-BDRMST算法。
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 ( 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.