DocumentCode
983389
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
Volume
8
Issue
5
fYear
1989
fDate
5/1/1989 12:00:00 AM
Firstpage
563
Lastpage
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
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;
fLanguage
English
Journal_Title
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher
ieee
ISSN
0278-0070
Type
jour
DOI
10.1109/43.24884
Filename
24884
Link To Document