Back to search

West Virginia University

Algorithmic Issues in some Disjoint Clustering Problems in Combinatorial Circuits

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
PhD
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Lane Department of Computer Science and Electrical Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Donovan, Zola Nailah

Subjects

dc:subject × 6

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
West Virginia University
Base URL
researchrepository.wvu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Donovan, Zola Nailah. Algorithmic Issues in some Disjoint Clustering Problems in Combinatorial Circuits. Dissertation thesis, https://doi.org/10.33915/etd.3721