A fast hypergraph min-cut algorithm for circuit partitioning

Wai-Kei Mak, D. F. Wong*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

28 Citations (Scopus)


Circuit partitioning is one of the central problems in VLSI system design. The primary objective of circuit partitioning is to minimize the number of interconnections between different components of the partitioned circuit. So the circuit partitioning problem is closely related to the minimum cut problem. Recently, two very fast algorithms for computing minimum cuts in graphs were reported. However, it is known that a circuit netlist cannot be accurately modeled by a graph, but only by a hypergraph. In this paper, we present the fastest algorithm known today for computing a minimum cut in a hypergraph which is a non-trivial extension of the result in Stoer and Wagner. Since the netlist of a circuit can be modeled naturally as a hypergraph, this opens the opportunity for finding very-high-quality solutions for the circuit partitioning problem. Unlike most minimum cut algorithms which rely on flow computations in a network, ours is a non-flow-based algorithm.

Original languageEnglish
Pages (from-to)1-11
Number of pages11
JournalIntegration, the VLSI Journal
Issue number1
Publication statusPublished - Nov 2000

Scopus Subject Areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering


Dive into the research topics of 'A fast hypergraph min-cut algorithm for circuit partitioning'. Together they form a unique fingerprint.

Cite this