Genetic algorithms for graph partitioning and incremental graph partitioning

Harpal Maini, Kishan Mehrotra, Chilukuri K Mohan, Sanjay Ranka

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Scopus citations

Abstract

Partitioning graphs into equally large groups of nodes, minimizing the number of edges between different groups, is an extremely important problem in parallel computing. This paper presents genetic algorithms for suboptimal graph partitioning, with new crossover operators (KNUX, DKNUX) that lead to orders of magnitude improvement over traditional genetic operators in solution quality and speed. Our method can improve on good solutions previously obtained by using other algorithms or graph theoretic heuristic in minimizing the total communication cost or the worst case cost of communication for a single processor. We also extend our algorithm to Incremental Graph Partitioning problems, in which the graph structure or system properties changes with time.

Original languageEnglish (US)
Title of host publicationProceedings of the ACM/IEEE Supercomputing Conference
Editors Anon
PublisherIEEE Computer Society
Pages449-457
Number of pages9
StatePublished - 1994
EventProceedings of the 1994 Supercomputing Conference - Washington, DC, USA
Duration: Nov 14 1994Nov 18 1994

Other

OtherProceedings of the 1994 Supercomputing Conference
CityWashington, DC, USA
Period11/14/9411/18/94

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Genetic algorithms for graph partitioning and incremental graph partitioning'. Together they form a unique fingerprint.

Cite this