Network-flow-based multiway partitioning with area and pin constraints

Huiqun Liu, D. F. Wong

Research output: Contribution to journalArticlepeer-review


Network flow is an excellent approach to finding min-cuts because of the celebrated max-flow min-cut theorem. For a long time, however, it was perceived as computationally expensive and deemed impractical for circuit partitioning. Recently, the algorithm FBB [1], [2] successfully applied network flow to two-way balanced partitioning. It for the first time demonstrated that network flow was a viable approach to circuit partitioning. In this paper, we present FBB-MW, which is an extension of FBB, to solve the problem of multiway partitioning with area and pin constraints. Experimental results show that FBB-MW outperforms previous approaches for multiple field programmable gate array partitioning. In particular, although FBB-MW does not employ logic replication and logic resynthesis, it still outperforms [5] and [6], which allow replication and resynthesis for optimization.

Original languageEnglish (US)
Pages (from-to)50-59
Number of pages10
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number1
StatePublished - 1998
Externally publishedYes


  • Circuit partitioning, field programmable gate array, integrated circuit design, network flow

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Network-flow-based multiway partitioning with area and pin constraints'. Together they form a unique fingerprint.

Cite this