LINEAR TIME ALGORITHMS FOR OPTIMAL CMOS LAYOUT.

Published

Journal Article

We consider the problem of efficient CMOS circuit layout which has been formulated into an interesting graph-theoretical problem. A linear-time algorithm is described for optimal layout of a graph when the circuit topology is fixed. A further linear-time algorithm is provided to determine an optimal layout (i. e. , having no diffusion gaps) when such a layout exists in some topology for the circuit. The key to our solution is a finite set of representative graphs which concisely describe topologically distinct paths in planar embedded series-parallel graphs.

Duke Authors

Cited Authors

  • Ravi Nair, ; Bruss, A; Reif, J

Published Date

  • December 1, 1985

Start / End Page

  • 327 - 338

Citation Source

  • Scopus