# A generational scheme for partitioning graphs

Soper, Alan and Walshaw, Christopher (2001) *A generational scheme for partitioning graphs.* In: Spector, Lee and Goodman, Erik D., (eds.) GECCO-2001: proceedings of the Genetic and Evolutionary Computation Conference: a joint meeting of the sixth annual Genetic Programming Conference (GP-2001) and the tenth International Conference on Genetic Algorithms (ICGA-2001): July 7-11, 2001. Morgan Kaufmann Publishers, San Francisco, USA, pp. 607-614. ISBN 978-1558607743

## Abstract

Graph partitioning divides a graph into several pieces by cutting edges. Very effective heuristic partitioning algorithms have been developed which run in real-time, but it is unknown how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. Distinctive features are the transmission and modification of whole subdomains (the partitioned units) that act as genes, and the use of a multilevel heuristic algorithm to effect the crossover and mutations. Its effectiveness is demonstrated by improvements on previously established benchmarks.

Item Type: | Book Section |
---|---|

Uncontrolled Keywords: | genetic programming, algorithms |

Subjects: | Q Science > QA Mathematics |

School / Department / Research Groups: | School of Computing & Mathematical Sciences 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:59 |

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

### Actions (login required)

View Item |