River routing in VLSI (Q1102106)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: River routing in VLSI |
scientific article; zbMATH DE number 4049038
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | River routing in VLSI |
scientific article; zbMATH DE number 4049038 |
Statements
River routing in VLSI (English)
0 references
1987
0 references
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.
0 references
VLSI layout
0 references
algorithm design technique
0 references
single-layer wiring
0 references
river routing
0 references
