Title :
On routing two-terminal nets in the presence of obstacles
Author :
JáJá, Joseph ; Wu, S.A.
Author_Institution :
Dept. of Electr. Eng., Maryland Univ., College Park, MD, USA
fDate :
5/1/1989 12:00:00 AM
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 :
circuit layout CAD; finding edge-disjoint paths; knock-knee model; number of vias; obstacles; optimization criteria; routability; routing two-terminal nets; standard two-layer model; total length of wires; Design automation; Joining processes; Polynomials; Routing; Wires; Wiring;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
