DocumentCode
912871
Title
A Linear-Time Routing Algorithm for Convex Grids
Author
Nishizeki, Takao ; Saito, Nobuji ; Suzuki, Kiminobu
Author_Institution
Department of Electrical Communications, Faculty of Engineering, Tohoku University, Sendai, Japan
Volume
4
Issue
1
fYear
1985
fDate
1/1/1985 12:00:00 AM
Firstpage
68
Lastpage
76
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.
Keywords
Circuits; Heuristic algorithms; Joining processes; Partitioning algorithms; Routing; Shape; Turning; Very large scale integration; Wiring;
fLanguage
English
Journal_Title
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher
ieee
ISSN
0278-0070
Type
jour
DOI
10.1109/TCAD.1985.1270099
Filename
1270099
Link To Document