An O(N) sorting algorithm for IC layout graph operation

被引：0

作者：

Li, G ^{[1
]}

Lin, ZH ^{[1
]}

Chen, HP ^{[1
]}

机构：

[1] Shanghai Jiao Tong Univ, VLSI Res Inst, Shanghai 200030, Peoples R China

来源：

PROCEEDINGS OF THE 6TH INTERNATIONAL CONFERENCE ON COMPUTER AIDED DESIGN & COMPUTER GRAPHICS | 1999年

关键词：

IC; layout verification; hierarchical; scan line; sorting;

D O I：

暂无

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Scan line algorithm is the main algorithm for IC layout graph operation, in which sorting costs considerable time. Usually the quick sorting algorithm whose time complexity is O(NlogN) in average, and O(N-2) in worst case ( N is the sum of sorted elements) is widely used. According to the characteristics of IC layout, we present a linear time complexity algorithm in this paper. For hierarchical designed IC layout, it has many advantages.

引用

页码：639 / 642

页数：4