On Routing Two-Terminal Nets in the Presence of Obstacles.
On Routing Two-Terminal Nets in the Presence of Obstacles.
Files
Publication or External Link
Date
1987
Authors
JaJa, Joseph F.
Wu, S.A.
Advisor
Citation
DRUM DOI
Abstract
We consider 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. Our main results are polynomial time algorithms to determine whether the given nets are routable in either model for any fixed k. We introduce a technique that reduces the general problem into finding edge-disjoint paths in a graph whose size is proportional to the size of the obstacles. Two optimization criteria are considered: the total length of the wires and the number of vias used.