New heuristic solution procedures for the uniform graph partitioning problem: Extensions and evaluation

The uniform graph partitioning problem can be described as partitioning the nodes of a graph into two sets of equal size to minimize the sum of the cost of arcs having end-points in different sets. This problem has important applications in VLSI design, computer compiler design, and in placement and layout problems. The problem is known to be NP-complete. In this paper the authors propose a new heuristic procedure for solving the graph partitioning problem. This heuristic is based on a genetic algorithm with features tailored for solving the graph partitioning problem. The authors also summarize a technique for obtaining good bounds for this problem, and compare and analyse the results from new as well as existing graph partitioning heuristics.