LINEAR TIME ALGORITHMS FOR OPTIMAL CMOS LAYOUT.

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 Scholars

Author John H. Reif Computer Science