Stretching a knock-knee layout for multilayer wiring

The problem of stretching a knock-knee layout in the knock-knee mode to ensure its wirability is considered. An optimal algorithm for the problem in two layers is presented. A 4/3 approximation algorithm for the corresponding problem in three layers, shown to be NP-complete, is devised.< >

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 1990-01, Vol.39 (1), p.148-151
Main Authors: Brady, M.L., Sarrafzadeh, M.
Format: Article
Language:English
Subjects:
Applied sciences
Circuits
Design. Technologies. Operation analysis. Testing
Electronics
Exact sciences and technology
Integrated circuits
Law
Legal factors
Nonhomogeneous media
Research and development
Routing
Semiconductor electronics. Microelectronics. Optoelectronics. Solid state devices
Tiles
Very large scale integration
Wires
Wiring
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The problem of stretching a knock-knee layout in the knock-knee mode to ensure its wirability is considered. An optimal algorithm for the problem in two layers is presented. A 4/3 approximation algorithm for the corresponding problem in three layers, shown to be NP-complete, is devised.< >
ISSN:0018-9340
1557-9956
DOI:10.1109/12.46293