Skip navigation

A generational scheme for partitioning graphs

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

Full text not available from this repository.

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
Pre-2014 Departments: 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: 11 Jul 2018 13:52
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/496

Actions (login required)

View Item View Item