Abstract

Partitioning is a fundamental problem with extensive applications to many areas, including data mining, parallel processing and the design of VLSI Circuit. We propose an effective multi-level algorithm based on Genetic Algorithm (GA) for bisecting graph. During its coarsening phase, we adopt an improved matching approach based on the global information of the graph core to develop its guidance function. During its refinement phase, we exploit the hybrid genetic refinement algorithm to find the global approximate biparitioning which incorporate early-exit FM (FM-EE) local improvement heuristic into GA. The success of our algorithm relies on exploiting both the GA and the concept of the graph core. It was implemented in ANSI C and compared to MeTiS that is a state-of-the-art partitioner in the literature. Our experimental evaluations show that it performs well and produces encouraging solutions on 18 different graphs benchmarks.

Paper Details