Efficient network flow based min-cut balanced partitioning

Honghua Yang, D. F. Wong

Research output: Chapter in book/report/conference proceedingChapterpeer-review

49 Citations (Scopus)


We consider the problem of bipartitioning a circuit into two balanced components that minimizes the number of crossing nets. Previously, the Kernighan and Lin type (K&L) heuristics, the simulated annealing approach, and the spectral method were given to solve the problem. However, network flow techniques were overlooked as a viable approach to min-cut balanced bipartition due to its high complexity. In this paper we propose a balanced bipartition heuristic based on repeated max-flow min-cut techniques, and give an efficient implementation that has the same asymptotic time complexity as that of one max-flow computation. We implemented our heuristic algorithm in a package called FBB. The experimental results demonstrate that FBB outperforms the K&L heuristics and the spectral method in terms of the number of crossing nets, and the efficient implementation makes it possible to partition large circuit instances with reasonable runtime. For example, the average elapsed time for bipartitioning a circuit S35932 of almost 20K gates is less than 20 minutes.

Original languageEnglish
Title of host publication1994 IEEE/ACM International Conference On Computer-aided Design, ICCAD 1994
Number of pages6
ISBN (Print)0818664177, 0818630108
Publication statusPublished - Nov 1994
Event1994 IEEE/ACM International Conference on Computer-aided Design, ICCAD 1994 - San Jose, United States
Duration: 6 Nov 199410 Nov 1994
https://ieeexplore.ieee.org/xpl/conhome/4983/proceeding (Link to conference proceedings)

Publication series

NameIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
ISSN (Print)1063-6757


Conference1994 IEEE/ACM International Conference on Computer-aided Design, ICCAD 1994
Country/TerritoryUnited States
CitySan Jose
Internet address

Scopus Subject Areas

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


Dive into the research topics of 'Efficient network flow based min-cut balanced partitioning'. Together they form a unique fingerprint.

Cite this