On the circuit implementation problem
W.-N. Li, Andrew E. B. Lim, Rahul Agrawal, Sartaj K. Sahni · 1992
Abstract-In this paper, we consider the problem of selecting an implementation of each circuit module from a cell library so as to satisfy overall delay and area (or delay and power) requirements. Two versions of the circuit implementation problem, basic circuit implementation problem and the general circuit implementation problem are shown to be NP-hard. A pseudo-polynomial time algorithm for the basic circuit imple-mentation problem on series-parallel circuits is developed, and heuristics for the basic circuit implementation problem on gen-eral circuits are formulated and experimented with. I.