Article ID: | iaor20062254 |
Country: | United Kingdom |
Volume: | 56 |
Issue: | 5 |
Start Page Number: | 549 |
End Page Number: | 562 |
Publication Date: | May 2005 |
Journal: | Journal of the Operational Research Society |
Authors: | Polat F., Kkpetek S., Ouztzn H. |
The graph partitioning problem is defined as that of dividing the vertices of an undirected graph into a set of balanced parts through the removal of a set of edges, whose size is to be minimized. A number of researchers have investigated multilevel schemes, which coarsen the graph by collapsing vertices and edges, partition the smaller graph, and then uncoarsen it to construct a partitioning of the original graph. In this paper, a genetic algorithm for the coarsening phase of a multilevel scheme for graph partitioning is presented. The proposed approach has been demonstrated to improve the solution quality at the expense of running time.