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 -