For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 1992/10/25
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)>>
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.