Ronald Fagin, Larry Stockmeyer
IJCV
A methodology of VLSI layout described by several authors first determines the relative positions of indivisible pieces, called cells, on the chip. Various optimizations are then performed on this initial layout to minimize some cost measure such as chip area or perimeter. If each cell is a rectangle with given dimensions, one optimization problem is to choose orientations of all the cells to minimize the cost measure. A polynomial time algorithm is given for this optimization problem for layouts of a special type called slicings. However, orientation optimization for more general layouts is shown to be NP-complete (in the strong sense). © 1983 Academic Press, Inc.
Ronald Fagin, Larry Stockmeyer
IJCV
Merrick Furst, Richard Lipton, et al.
Information and Control
Moni Naor, Larry Stockmeyer
STOC 1993
Larry Stockmeyer, Dharmendra S. Modha
IEEE Trans. Inf. Theory