Heuristics for graph decomposition

Abstract

The problem addressed in this paper is that of decomposing a weighted graph into a specified number of subgraphs such that these subgraphs have balanced sums of vertex weights and minimal sums of edge weights. To find a reasonable solution to this intractable problem, we suggest an approximate objective function that can be minimized by heuristic procedures. The heuristic procedure that we propose is based on a hybrid genetic algorithm (HGA) for decomposing a graph followed by an iterative improvement heuristic for tuning the HGA's results. We applied our proposed heuristics to several graphs and obtained promising results.