Genetic algorithm and graph partitioning

Thang Nguyen Bui, Byung Ro Moon

Research output: Contribution to journalArticlepeer-review

268 Scopus citations


Hybrid genetic algorithms (GAs) for the graph partitioning problem are described. The algorithms include a fast local improvement heuristic. One of the novel features of these algorithms is the schema preprocessing phase that improves GAs' space searching capability, which in turn improves the performance of GAs. Experimental tests on graph problems with published solutions showed that the new genetic algorithms performed comparable to or better than the multistart Kernighan-Lin algorithm and the simulated annealing algorithm. Analyses of some special classes of graphs are also provided showing the usefulness of schema preprocessing and supporting the experimental results.

Original languageEnglish (US)
Pages (from-to)841-855
Number of pages15
JournalIEEE Transactions on Computers
Issue number7
StatePublished - 1996

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Genetic algorithm and graph partitioning'. Together they form a unique fingerprint.

Cite this