text: The modern integrated circuit is one of the most complex products that has been engineered to-date. It continues to grow in complexity as the years progress. As a result, very large-scale integrated (VLSI) circuit design now involves massive design teams employing state-of-the art computer-aided design (CAD) tools. One of the oldest, yet most important CAD problems for VLSI circuits is physical design automation, where one needs to compute the best physical layout of millions to billions of circuit components on a tiny silicon surface Lim08 . The process of mapping an electronic design to a chip involves a number of physical design stages, one of which is clustering. In this paper, we focus on problems in clustering which are critical for more sustainable chips. The clustering problem in combinatorial circuits alone is a source of multiple models. In particular, we consider the problem of clustering combinatorial circuits for delay minimization, when logic replication is not allowed ( CN ). The problem of delay minimization when logic replication is allowed ( CA ) has been well studied, and is known to be solvable in polynomial-time Wong1 . However, unbounded logic replication can be quite expensive. Thus, CN is an important problem. We show that selected variants of CN are NP-hard . We also obtain approximability and inapproximability results for these problems. A preliminary version of this paper appeared in Don15 .
  @cite_5: The authors address the problem of clustering a circuit for minimizing its delay, subject to capacity constraints on the clusters. They present an algorithm for combinational circuits and give sufficient conditions under which it is optimum. In addition, they address the problem of minimizing the number of clusters and nodes without increasing the maximum delay found by the algorithm. Finally, they extend the clustering algorithm to minimize the clock cycle of a sequential synchronous circuit. >
  @cite_2: This paper addresses the problem of circuit clustering for delay minimization, subject to capacity constraints. We use the general delay model, for which only heuristic solutions were known. We present an optimal polynomial time algorithm for combinational circuits under this model. Our algorithm can be generalized to solve the problem under any monotone clustering constraint.
  @cite_8: An important aspect of the packaging of digital networks is the allocation of logic gates to modules such that a predetermined objective function is minimized. In order to develop techniques for this partitioning of a logic network we have considered the following problem: Given an acyclic combinational network composed of various primitive blocks such as NOR gates, assume that a maximum of M gates can be "clustered" together into larger modules, and that a maximum of P pins can be accommodated in each larger module. Assume also that in a network composed of such larger modules, no delay is encountered on the interconnections linking two gates internal to a module and a delay of one time unit is encountered on interconnections linking two gates in different modules . Find an easily applied algorithm that will result in a network such that the maximum delay through the network is minimized.
summary: In @cite_8 a polynomial-time optimal solution to the clustering problem is given assuming the unit delay model. In this model, there is no delay that is associated with any gate or with any edge linking two gates within a cluster. A delay of one unit of time is assumed along any edge crossing a cluster boundary. Let us note that in that paper replication of the logic is allowed, that is, a node may be present in many clusters. The more general delay model considered in this paper is presented in @cite_5 . In that paper an algorithm is given that constructs a clustering that aims to minimize the delay under the general delay model. Let us note that the algorithm achieves optimum delay under some specific conditions. In @cite_2 another clustering algorithm is presented, and in the same paper it is proved that the algorithm always finds the optimum clustering.