An Efficient Hypergraph Bisection Algorithm for Partitioning VLSI Circuits

Yoko KAMIDOI  Shin'ichi WAKABAYASHI  Noriyoshi YOSHIDA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E75-A   No.10   pp.1272-1279
Publication Date: 1992/10/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
hypergraph,  bisection,  netgraph,  circuit partitioning,  

Full Text: PDF(699.9KB)>>
Buy this Article

This paper presents an efficient heuristic algorithm for min-cut bisection of weighted hypergraphs. The proposed algorithm is based on a heuristic algorithm proposed by Kahng, which was devised for non-weighted hypergraph bisection, adopting a non-weighted graph called intersection graph to represent a given hypergraph. In the proposed algorithm, instead of an intersection graph, a bipartite graph called netgraph is newly introduced to explicitly represent the weights of nodes of a hypergraph. Using the netgraph, it is easy to partition a weighted hypergraph into two hypergraphs with same size. Computation time of the proposed method is O(m2), where m is the number of nodes of a given hypergraph. Experimental results with real circuit data show that the proposed method produces better solutions in shorter computation time compared with existing methods.