Skip to main content
Article
Single-Layer Channel Routing and Placement with Single-Sided Nets
Computers & Mathematics With Applications
  • Ronald I. Greenberg
  • Jau-Der Shih
Document Type
Article
Publication Date
8-1-1996
Pages
1--7
Publisher Name
Elsevier
Abstract

This paper considers the optimal offset, feasible offset, and optimal placement problems for a more general form of single-layer VLSI channel routing than has usually been considered in the past. Most prior works require that every net has exactly one terminal on each side of the channel. As long as only one side of the channel contains multiple terminals of the same net, we provide linear-time solutions to all three problems. Such results are implausible if the placement of terminals is entirely unrestricted; in fact, the size of the output for the feasible offset problem may be Ω(n^2). The linear-time results also hold with a ragged boundary on the side of the channel with multiple connections to the same net.

Creative Commons License
Creative Commons Attribution-Noncommercial-No Derivative Works 3.0
Citation Information
Ronald I. Greenberg and Jau-Der Shih. Single-layer channel routing and placement with single-sided nets. Computers \& Mathematics With Applications, 32(4):1--7, August 1996.