Affordable Access

Publisher Website

One-layer routing without component constraints

Authors
Journal
Journal of Computer and System Sciences
0022-0000
Publisher
Elsevier
Publication Date
Volume
28
Issue
3
Identifiers
DOI: 10.1016/0022-0000(84)90022-9
Disciplines
  • Computer Science

Abstract

Abstract We consider the problem of wiring together, in one layer, corresponding pairs of terminals located on either a printed circuit board (PCB) or on a VLSI chip. We assume that the terminals are located in two parallel rows on opposite sides of a channel. The channel width may either be fixed or variable. We further assume that the components (on which the terminals lie) do not restrict the routing. Corresponding to various natural restrictions that may be placed on the wiring, we define two classes of layouts and give polynomial-time algorithms which produce optimal layouts within the respective classes. In addition, we derive bounds which show that the layouts in one class may be significantly more compact than those in the other. The results which we present are applicable to PCB technology without qualification. With respect to VLSI technology, the results are applicable provided that a separate layer is available for routing. That is, a layer which is effectively insulated from the active circuits of the components. In addition, we show how one-layer routings obtained under the no component constraint assumption can be utilized for two-layer routing under a conventional VLSI model (i.e., one with component constraints).

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Strategy of one and half layer routing

on Microprocessing and Microprogr... Jan 01, 1991

VRP12 (vehicle routing problem with distances one...

on International Journal of Produ...

Physical layer impairment aware wavelength routing...

on Optics Communications Jan 01, 2007
More articles like this..