On routing two-terminal nets in the presence of obstacles
| Title | On routing two-terminal nets in the presence of obstacles |
| Publication Type | Journal Articles |
| Year of Publication | 1989 |
| Authors | JaJa JF, Wu SA |
| Journal | Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on |
| Volume | 8 |
| Issue | 5 |
| Pagination | 563 - 570 |
| Date Published | 1989/05// |
| ISBN Number | 0278-0070 |
| 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 |
| 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 |
| DOI | 10.1109/43.24884 |