AN EFFICIENT ONE-SIDE HEIGHT MINIMIZATION ALGORITHM FOR ROUTING AROUND A RECTANGLE

作     者：TEO, KH TUAN, TC 

作者机构：NATL SUN YAT SEN UNIVINST APPL MATHCOMP SCI PROGRAMKAOHSIUNGTAIWAN 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：1992年第44卷第2期

页      面：101-105页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：ANALYSIS OF ALGORITHMS DATA STRUCTURES DESIGN OF ALGORITHMS DETAILED ROUTING AROUND A RECTANGLE OPTIMIZATION PRIORITY QUEUE GRID-BASED WIRING VLSI 

摘      要：An h by w rectangular module is embedded in a unit grid with a set S of terminals residing along the edges of the module. The terminals are located on the grid points. S is partitioned into m nets which constitute the net set N. All terminals of a net must be connected by a 2-layer rectilinear wire which consists of the grid line segments and satisfies the following constraints: 1. Horizontal segments are in one layer and vertical segments are in the other layer. 2. Two wires can only meet at grid points. 3. Wires can only run through the exterior of the rectangular module. The problem of finding a wiring which minimizes the area of the enclosing rectangle containing both the module and the connecting wires is called the optimal routing around one module. The problem of wiring around a module with terminals on 2 opposite sides only occurs often since it is often desirable to simplify the placement and routing process. An O(m log log m) time algorithm, where m is the number of nets and the set TOP is initially sorted, is used to tackle the one-side height minimization problem for the 2-layer rectilinear wiring around a rectangular module.