Soper, Alan ORCID: 0000-0002-0901-9803 and Walshaw, Christopher ORCID: 0000-0003-0253-7779 (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:	30 Sep 2019 13:46
URI:	http://gala.gre.ac.uk/id/eprint/496

Actions (login required)

View Item