ON THE M-WAY GRAPH PARTITIONING PROBLEM

The m-way graph partitioning problem (GPP) is an intractable combinato rial optimization problem with many important applications in the desi gn automation of VLSI circuits and in the mapping problem for distribu ted computing systems. In this paper, we introduce a technique based o n a problem-space genetic algorithm (PSGA) for the GPP to reduce the w eighted cut-size while keeping the size of each subset balanced. The p roposed PSGA based approach integrates a problem-specific simple and f ast heuristic with a genetic algorithm to search a large solution spac e efficiently and effectively to find the best possible solution in an acceptable CPU time. Experimental study shows that our technique prod uces better results with respect to both the quality of the solution a nd the computational time over the previous work. The PSGA is a simple , versatile and a generic optimization technique which can also be app lied to other combinatorial optimization problems.