Genetic algorithms for graph partitioning and incremental graph partitioning
Open Access
- 17 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Partitioning graphs into equally large groups of nodes, minimizing the number of edges between different groups, is an extremely important problem in parallel computing. This paper presents genetic algorithms for suboptimal graph partitioning, with new crossover operators (KNUX, DKNUX) that lead to orders of magnitude improvement over traditional genetic operators in solution quality and speed. Our method can improve on good solutions previously obtained by using other algorithms or graph theoretic heuristics in minimizing the total communication cost or the worst case cost of communication for a single processor. We also extend our algorithm to Incremental Graph Partitioning problems, in which the graph structure or system properties changes with time.Keywords
This publication has 3 references indexed in Scilit:
- Performance of dynamic load balancing algorithms for unstructured mesh calculationsConcurrency: Practice and Experience, 1991
- Partitioning of unstructured problems for parallel processingComputing Systems in Engineering, 1991
- Partitioning Sparse Matrices with Eigenvectors of GraphsSIAM Journal on Matrix Analysis and Applications, 1990