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-1558607743Full text not available from this repository.
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.
Actions (login required)