Routing through a rectangleRouting through a rectangle

Access Restriction
Subscribed

 Author Mehlhorn, K. ♦ Preparata, F. P. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1986 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract In this paper an $\textit{O}(\textit{N}$ log $\textit{N})$ algorithm for routing through a rectangle is presented. Consider an $\textit{n}-by-\textit{m}$ rectangular grid and a set of $\textit{N}$ two-terminal nets. A net is a pair of points on the boundary of the rectangle. A layout is a set of edge-disjoint paths, one for each net. Our algorithm constructs a layout, if there is one, in $\textit{O}(\textit{N}$ log $\textit{N})$ time; this contrasts favorably with the area of the layout that might be as large as $\textit{N}2.$ The layout constructed can be wired using four layers of interconnect with only $\textit{O}(\textit{N})$ contact cuts. A partial extension to multiterminal nets is also discussed. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1986-01-02 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 33 Issue Number 1 Page Count 26 Starting Page 60 Ending Page 85

Open content in new tab

Source: ACM Digital Library