scientific article; zbMATH DE number 3907789
[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.
- A polynomial time algorithm for 2-layer channel routing problem
- scientific article; zbMATH DE number 1538069
- An efficient lower bound algorithm for channel routing
- An algorithm for finding a non-trivial lower bound for channel routing
- ROUTING ALGORITHMS FOR DOUBLE LOOP NETWORKS
- Channel routing of multiterminal nets
- Nearly optimal algorithms and bounds for multilayer channel routing
- One-layer routing without component constraints
- Channel routing in knock-knee mode: Simplified algorithms and proofs
- Two-layer channel routing with vertical unit-length overlap
- Minimum separation for single-layer channel routing
- A parallel multi-layer channel router on the HVH model
- An efficient lower bound algorithm for channel routing
- Routing through a Dense Channel with Minimum Total Wire Length
- Parallel Algorithms for Channel Routing in the Knock-Knee Model
- scientific article; zbMATH DE number 3898776 (Why is no real title available?)
- Optimal Three-Layer Channel Routing
- A Provably Good Algorithm for the Two Module Routing Problem
- scientific article; zbMATH DE number 4035743 (Why is no real title available?)
- Maximum alignment of interchangeable terminals
- scientific article; zbMATH DE number 52189 (Why is no real title available?)
- OPTIMAL ROUTING THROUGH DENSE CHANNELS
- Channel routing of multiterminal nets
- Nearly optimal algorithms and bounds for multilayer channel routing
- scientific article; zbMATH DE number 1737512 (Why is no real title available?)
- 3-dimensional single active layer routing
- Distribution of the Minimum Channel Width in VLSI Wiring
- scientific article; zbMATH DE number 4118301 (Why is no real title available?)
- scientific article; zbMATH DE number 3893100 (Why is no real title available?)
- An algorithm for routing problems with given horizontal constraint graph
- A parallel algorithm for channel routing
- Optimal multilayer channel routing with overlap
- Routing in times square mode
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)