Wiring knock-knee layouts: a global approach

Author

Sarrafzadeh, Majid ; Wagner, Dorothea ; Wagner, Frank ; Weihe, Karsten

Author_Institution

Dept. of Electr. Eng. & Comput. Sci., Northwestern Univ., Evanston, IL, USA

Volume

43

Issue

5

fYear

1994

fDate

5/1/1994 12:00:00 AM

Firstpage

581

Lastpage

589

Abstract

Presents a global approach to solve the three-layer wirability problem for knock-knee layouts. In general, the problem is NP-complete. Only for very restricted classes of layouts polynomial three-layer wiring algorithms are known up to now. The authors show that for a large class of layouts a three-layer wiring can be constructed by solving a path problem in a special class of graphs or a two-satisfiability problem, and thus may be wired in time linear in the size of the layout area. Moreover, it is shown that a minimum stretching of the layout into a layout belonging to this class can be found by solving a clique cover problem in an interval graph. This problem is solvable in time linear in the size of the layout area as well. Altogether, the method also yields a good heuristic for the three-layer wirability problem for knock-knee layouts

Keywords

algorithm theory; circuit layout CAD; network routing; NP-complete; clique cover problem; knock-knee layouts; layout area; three-layer wirability problem; three-layer wiring; two-satisfiability problem; Computer science; Integrated circuit yield; Joining processes; Knee; Partitioning algorithms; Polynomials; Process design; Routing; Wires; Wiring;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.280805

Filename

280805