Date of Graduation
Statler College of Engineering and Mineral Resources
Lane Department of Computer Science and Electrical Engineering
David W. Graham
David W. Graham
Vahan V. Mkrtchyan
Daryl S. Reynolds
Frances L. VanScoy
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 this problem, one needs 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 exist several models for the clustering problem. In particular, we consider the problem of disjoint clustering in combinatorial circuits for delay minimization (CN). The problem of clustering with replication for delay minimization has been well-studied and known to be solvable in polynomial time. However, replication can become expensive when it is unbounded.
Consequently, CN is a problem worth investigating. In this dissertation, we establish the computational complexities of several variants of CN. We also present approximation and exact exponential algorithms for some variants of CN. In some cases, we even obtain an approximation factor of strictly less than two. Furthermore, our exact exponential algorithms beat brute force.
Donovan, Zola Nailah, "Algorithmic Issues in some Disjoint Clustering Problems in Combinatorial Circuits" (2018). Graduate Theses, Dissertations, and Problem Reports. 3721.