Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

An Effective Multilevel Memetic Algorithm for Balanced Graph Partitioning

Abstract :

The balanced graph partitioning consists in dividing the vertices of an undirected graph into a given number of subsets of approximately equal size, such that the number of edges crossing the subsets is minimized. In this work, we present a multilevel memetic algorithm for this NP-hard problem that relies on a powerful grouping recombination operator and a dedicated local search procedure. The proposed operator tends to preserve the backbone with respect to a set of parent individuals, i.e. the grouping of vertices which is same throughout each parent individual. Although our approach requires significantly longer computing time compared to some current state-of-art graph partitioning algorithms such as SCOTCH, METIS, CHACO, JOSTLE, etc., it competes very favorably with these approaches in terms of solution quality. Moreover, it easily reaches or improves on the best partitions ever reported in the literature.

Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03255385
Contributeur : Okina Université d'Angers <>
Soumis le : mercredi 9 juin 2021 - 15:04:12
Dernière modification le : jeudi 10 juin 2021 - 03:39:57

Lien texte intégral

Identifiants

Collections

Citation

Una Benlic, Jin-Kao Hao. An Effective Multilevel Memetic Algorithm for Balanced Graph Partitioning. 22nd IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2010, Arras, France. pp.121 - 128, ⟨10.1109/ICTAI.2010.25⟩. ⟨hal-03255385⟩

Partager

Métriques

Consultations de la notice

4