Abstract | ||
---|---|---|
In this paper, we consider the channel routing problem involving two-terminal nets on rectilinear grids. An efficient algorithm is described which necessarily finds a routing in a given grid whenever it exists. The algorithm is not a heuristic but an exact one, and works for a rather large class of grids, called convex grids, including the grids of rectangular, T-, L-, or X-shape boundaries. Both the running time and required space are linear in the number of vertices of a grid. |
Year | DOI | Venue |
---|---|---|
1985 | 10.1109/TCAD.1985.1270099 | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |
Keywords | DocType | Volume |
convex grid,large class,rectilinear grid,Convex Grids,two-terminal net,Linear-Time Routing Algorithm,required space,X-shape boundary,efficient algorithm | Journal | 4 |
Issue | ISSN | Citations |
1 | 0278-0070 | 15 |
PageRank | References | Authors |
1.87 | 3 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Takao Nishizeki | 1 | 1771 | 267.08 |
N. Saito | 2 | 228 | 44.77 |
K. Suzuki | 3 | 15 | 1.87 |