D3G2A: The Dynamic Distributed Double Guided Genetic Algorithm for the K-Graph Partitioning Problem

L. Derbali, S. Bouamama, M. Hammami, and K. Ghdira (Tunisia)


Genetic algorithm, multi-agent systems, guidance, graph partitioning problem, multilevel graph partitioning.


Graph Partitioning has several important applications in Computer Science, including VLSI circuit layout, image processing, and distributing workloads for parallel computation. It is known to be NP-hard. In this paper we present in detail the K-Graph Partitioning Problem and the Dynamic Distributed Double Guided Genetic Algorithm. This algorithm consists of agents dynamically created and cooperated in order to solve the problem. Each agent performs its own genetic algorithm, guided by the min conflict-heuristic. The paper also presents the results of application the algorithm for the $K$-Graph Partitioning Problem using a multilevel paradigm.

Important Links:

Go Back