Title :
Graph partitioning using genetic algorithms with ODPX
Author :
Cincotti, A. ; Cutello, V. ; Pavone, M.
Author_Institution :
Dept. of Math. & Comput. Sci., Catania Univ., Italy
Abstract :
In this paper, we study approximate solutions to the extension of the "maximally balanced connected partition problem", whose corresponding decision problem is known to be 𝒩𝒫-complete. We introduce a genetic algorithm with a new crossover operator, called the "order- and distance-preserving crossover" (ODPX) operator, and we compare the results of our algorithm to a well-known deterministic approximation algorithm
Keywords :
approximation theory; computational complexity; genetic algorithms; graph theory; mathematical operators; NP-complete decision problem; ODPX operator; approximate solutions; deterministic approximation algorithm; genetic algorithms; graph partitioning; maximally balanced connected partition problem; order and distance-preserving crossover operator; Approximation algorithms; Biological cells; Computer science; Genetic algorithms; Genetic programming; Mathematics; Partitioning algorithms;
Conference_Titel :
Evolutionary Computation, 2002. CEC '02. Proceedings of the 2002 Congress on
Conference_Location :
Honolulu, HI
Print_ISBN :
0-7803-7282-4
DOI :
10.1109/CEC.2002.1006268
