# A combined evolutionary search and multilevel optimisation approach to graph-partitioning

Soper, Alan, Walshaw, Christopher and Cross, Mark (2004) *A combined evolutionary search and multilevel optimisation approach to graph-partitioning.* Journal of Global Optimization, 29 (2). pp. 225-241. ISSN 0925-5001 (print) 1573-2916 (electronic)

## Abstract

The graph-partitioning problem is to divide a graph into several pieces so that the number of vertices in each piece is the same within some defined tolerance and the number of cut edges is minimised. Important applications of the problem arise, for example, in parallel processing where data sets need to be distributed across the memory of a parallel machine. Very effective heuristic algorithms have been developed for this problem which run in real-time, but it is not known how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. A distinctive feature is the use of a multilevel heuristic algorithm to provide an effective crossover. The technique is tested on several example graphs and it is demonstrated that our method can achieve extremely high quality partitions significantly better than those found by the state-of-the-art graph-partitioning packages.

Item Type: | Article |
---|---|

Uncontrolled Keywords: | evolutionary search, genetic algorithms, graph-partitioning, multilevel optimisation, |

Subjects: | Q Science > QA Mathematics |

School / Department / Research Groups: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Centre for Numerical Modelling & Process Analysis School of Computing & Mathematical Sciences > Centre for Numerical Modelling & Process Analysis > Computational Science & Engineering Group School of Computing & Mathematical Sciences > Computer & Computational Science Research Group School of Computing & Mathematical Sciences > Department of Computer Science School of Computing & Mathematical Sciences > Department of Mathematical Sciences |

Last Modified: | 20 Jun 2011 11:48 |

URI: | http://gala.gre.ac.uk/id/eprint/815 |

### Actions (login required)

View Item |