Back to Search
Start Over
Multilevel graph partitioning. an evolutionary approach
- Source :
- Journal of the Operational Research Society. May, 2005, Vol. 56 Issue 5, p549, 14 p.
- Publication Year :
- 2005
-
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. Keywords: graph partitioning problem; multilevel graph partitioning; genetic algorithms
- Subjects :
- Graph theory -- Analysis
Genetic algorithms
Business
Business, general
Subjects
Details
- Language :
- English
- ISSN :
- 01605682
- Volume :
- 56
- Issue :
- 5
- Database :
- Gale General OneFile
- Journal :
- Journal of the Operational Research Society
- Publication Type :
- Academic Journal
- Accession number :
- edsgcl.132270421