Title :
On optimum single-row routing
Author :
Kuh, Ernest S. ; Kashiwabara, Toshinobu ; Fujisawa, Toshio
fDate :
6/1/1979 12:00:00 AM
Abstract :
The problem of single-row routing represents the backbone of the problem of general routing of multilayer printed circuit boards. In this paper, the necessary and sufficient condition for optimum single-row routing is obtained. By optimum routing we mean minimumm street congestion. A novel formulation is introduced. Examples are given to illustrate how optimum routings are derived. A graph theory interpretation of the condition is also given.
Keywords :
Large-scale networks and systems; Layout; Design automation; Graph theory; Integrated circuit interconnections; Microelectronics; Nonhomogeneous media; Packaging; Printed circuits; Routing; Spine; Sufficient conditions;
Journal_Title :
Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCS.1979.1084650
