scientific article; zbMATH DE number 3907789

From MaRDI portal
Publication:3685216





[For the entire collection see Zbl 0561.00020.] In this paper we show that any two-terminal channel routing problem of density d can be solved in a two-layer grid of width \(\omega =(3/2)d+O(1)\) by using a model in which two wires are permitted to overlap for not more than a constant distance. This is an asymptotical improvement over the best known result \(\omega =2d-1\). The algorithm presented here has the following additional properties: (i) there are at most 6 pairs of overlapping edges for any two wires produced by it, (ii) it uses 6n contacts, where n is the number of nets to be connected, (iii) it can be implemented to run in time O(n). An extension of the algorithm to the multi-terminal problem is also discussed.




Cited in
(26)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3685216)