Multilevel graph partitioning: an evolutionary approach

Multilevel graph partitioning: an evolutionary approach

0.00 Avg rating0 Votes
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: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.