The main result of this well written and interesting paper is an O(n) time algorithm for the optimum offset problem in single-layer river routing. The result is achieved using a halving technique which is claimed to be new, but is merely a variant of the old divide-and-conquer paradigm. Algorithms for the minimum area, minimum longest wire length and minimum total wire length problems are also given that take \(O(n^ 2)\) time.
Recommendations
Cites work
- An optimal solution to a wire-routing problem
- Generalized Selection and Ranking: Sorted Matrices
- scientific article; zbMATH DE number 3858396 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- Optimal Placement for River Routing
- Scaling algorithms for network problems
- Selection in \(X+Y\) and matrices with sorted rows and columns
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
Cited in
(15)- Minimum separation for single-layer channel routing
- An efficient one-side height minimization algorithm for routing around a rectangle
- Single-layer channel routing and placement with single-sided nets
- A new measure of presortedness
- Faster goal-oriented shortest path search for bulk and incremental detailed routing
- River Routing with a Small Number of Jogs
- Optimal Placement for River Routing
- scientific article; zbMATH DE number 3958751 (Why is no real title available?)
- Some Geometry for General River Routing
- Offset range problem for two blocks
- DRAWING WITH FAT EDGES
- Minimum area joining of k compacted cells
- River routing with a generalized model
- Single jog minimum area joining of compacted cells
- Performance analysis of greedy heuristic to find a minimum total-jogs layout for river routing
This page was built for publication: River routing in VLSI
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102106)
