Publications [#237095] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Ravi Nair; Bruss, A; Reif, J, LINEAR TIME ALGORITHMS FOR OPTIMAL CMOS LAYOUT., undefined (December, 1985), pp. 327-338 (VLSI: Algorithms and Architectures, North-Holland Pub., pp. 327-338.) [pdf]
   (last updated on 2026/01/14)

   Abstract:
   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.