1993/01/01 by Jason Cong, M. E. Gonzalez Smith · 145 citations
Computer Science · Engineering · #Algorithm #Artificial intelligence #Automation #Citation #Cluster analysis #Computer science #Electronic design automation #Embedded Systems Design Techniques #Embedded system #Engineering #Parallel computing #VLSI and Analog Circuit Testing #VLSI and FPGA Design Techniques #Very-large-scale integration #World Wide Web
paper · pdf · doi:10.1145/157485.165119
openalex publication_date 1993/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
In thk paper, we present a bottom-up clustering algorithm based on recursive collapsing of small cliques in a graph. The sizes of the small cliques are derived using random graph theory. This clustering algorithm leads to a natural parallel implementation in which multiple processors are used to identify clusters simultaneously. We also present a cluster-based partitioning method in which our clustering algorithm is used as a preprocessing step to both the bisection algorithm by Fiduccia and Mattheyses and a ratio-cut algorithm by Wei and Cheng. Our results show that cluster-based partitioning obtains cut sizes up to 49.6% smaller than the bisection algorithm, and obtains ratio cut sizes up to 66.8% smaller than the ratio-cut algorithm. Moreover, we show that cluster-based partitioning produces much stabler results than direct partitioning.