Name
Abstract | ||
|---|---|---|
A genetic algorithm for partitioning a hypergraph into two disjoint graphs of minimum ratio cut is presented. As the Fiduccia-Mattheyses graph partitioning heuristic turns out to be not effective when used in the context of a hybrid genetic algorithm, we propose a modification of the Fiduccia-Mattheyses heuristic for more effective and faster space search by introducing a number of novel features. We also provide a preprocessing heuristic for genetic encoding designed solely for hypergraphs which helps genetic algorithms exploit clustering information of input graphs. Supporting combinatorial arguments for the new preprocessing heuristic are also provided. Experimental results on industrial benchmarks circuits showed visible improvement over recently published algorithms with a lower growth rate of running time |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1109/43.700718 | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |
Keywords | DocType | Volume |
combinatorial argument,preprocessing heuristic,genetic encoding,fiduccia-mattheyses heuristic,fiduccia-mattheyses graph,circuit ratio-cut partitioning,hybrid genetic algorithm,circuit optimisation,combinatorial mathematics,Fiduccia-Mattheyses heuristic,disjoint graph,genetic algorithm,genetic algorithms,graph theory,space search,hypergraph,GRCA,new preprocessing heuristic,clustering | Journal | 17 |
Issue | Citations | PageRank |
3 | 9 | 0.56 |
References | Authors | |
33 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thang Nguyen Bui | 1 | 769 | 129.78 |
| Byung-Ro Moon | 2 | 844 | 58.71 |