TY - JOUR
T1 - On routing two-terminal nets in the presence of obstacles
JF - Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Y1 - 1989
A1 - JaJa, Joseph F.
A1 - Wu,S.A.
KW - CAD;
KW - criteria;routability;routing
KW - edge-disjoint
KW - finding
KW - Layout
KW - length
KW - model;number
KW - model;total
KW - nets;standard
KW - of
KW - paths;knock-knee
KW - two-layer
KW - two-terminal
KW - vias;obstacles;optimization
KW - wires;circuit
AB - Consideration is given to the problem of routing k two-terminal nets in the presence of obstacles in two models: the standard two-layer model and the knock-knee model. Determining routability is known to be NP-complete for arbitrary k. The authors introduce a technique that reduces the general problem into finding edge-disjoint paths in a graph whose size depends only on the size of the obstacles. Two optimization criteria are considered: the total length of the wires and the number of vias used
VL - 8
SN - 0278-0070
CP - 5
M3 - 10.1109/43.24884
ER -