@article {14996,
title = {On routing two-terminal nets in the presence of obstacles},
journal = {Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on},
volume = {8},
year = {1989},
month = {1989/05//},
pages = {563 - 570},
abstract = {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},
keywords = {CAD;, criteria;routability;routing, edge-disjoint, finding, Layout, length, model;number, model;total, nets;standard, of, paths;knock-knee, two-layer, two-terminal, vias;obstacles;optimization, wires;circuit},
isbn = {0278-0070},
doi = {10.1109/43.24884},
author = {JaJa, Joseph F. and Wu,S.A.}
}