Analyzing Clustering and Partitioning Problems in Selected VLSI Models

As the modern integrated circuit continues to grow in complexity, the design of very large-scale integrated (VLSI) circuits involves massive teams employing state-of-the-art computer-aided design (CAD) tools. An old yet significant CAD problem for VLSI circuits is physical design automation. In physical design automation, we need to compute the best physical layout of millions to billions of circuit components on a tiny silicon surface. The process of mapping an electronic design to a chip involves several physical design stages, one of which is clustering. Even for combinatorial circuits, there are several models for the clustering problem. In particular, we consider the problem of clustering without replication in combinatorial circuits with a view towards minimizing delay (CN). The corresponding problem with replication has been well-studied and solvable in polynomial time. However, replication can become expensive when it is unbounded. Consequently, CN is a problem worth investigating. We establish the computational complexities of several variants of CN. Additionally, we obtain approximability and inapproximability results for some NP-hard variants of CN. We also present approximation and exact exponential algorithms for some variants of CN. We prove that for some cases there exists an approximation factor of strictly less than two and that our exact exponential algorithms beat brute force. Furthermore, we provide the first parameterized approximation algorithm in which the approximation ratio is also a parameter.