IEICE TRANSACTIONS on Fundamentals
An Efficient Hypergraph Bisection Algorithm for Partitioning VLSI Circuits
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E75-A No.10 pp.1272-1279
- Publication Date
- 1992/10/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yoko KAMIDOI, Shin'ichi WAKABAYASHI, Noriyoshi YOSHIDA, "An Efficient Hypergraph Bisection Algorithm for Partitioning VLSI Circuits" in IEICE TRANSACTIONS on Fundamentals,
vol. E75-A, no. 10, pp. 1272-1279, October 1992, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e75-a_10_1272/_p
Copy
@ARTICLE{e75-a_10_1272,
author={Yoko KAMIDOI, Shin'ichi WAKABAYASHI, Noriyoshi YOSHIDA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Efficient Hypergraph Bisection Algorithm for Partitioning VLSI Circuits},
year={1992},
volume={E75-A},
number={10},
pages={1272-1279},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={October},}
Copy
TY - JOUR
TI - An Efficient Hypergraph Bisection Algorithm for Partitioning VLSI Circuits
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1272
EP - 1279
AU - Yoko KAMIDOI
AU - Shin'ichi WAKABAYASHI
AU - Noriyoshi YOSHIDA
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E75-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 1992
AB - 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.
ER -
English
