A new method, the fusion fission, for the relaxed k-way graph partitioning problem, and comparisons with some multilevel algorithms

Abstract : In this paper a new graph partitioning problem is introduced, the relaxed k-way graph partitioning problem. It is close to the k-way, also called multi-way, graph partitioning problem, but with relaxed imbalance constraints. This problem arises in the air traffic control area. A new graph partitioning method is presented, the Fusion Fission, which can be used to resolve the relaxed k-way graph partitioning problem. The Fusion Fission method is compared to classical Multilevel packages and with a Simulated Annealing algorithm. The Fusion Fission algorithm and the Simulated Annealing algorithm, both require a longer computation time than the Multilevel algorithms, but they also find better partitions. However, the Fusion Fission algorithm partitions the graph with a smaller imbalance and a smaller cut than Simulated Annealing does.
Type de document :
Article dans une revue
Journal of Mathematical Modelling and Algorithms, Springer Verlag, 2007, 6 (3), pp 319-344. 〈10.1007/s10852-007-9059-4〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal-enac.archives-ouvertes.fr/hal-01021583
Contributeur : Laurence Porte <>
Soumis le : jeudi 20 novembre 2014 - 16:08:31
Dernière modification le : lundi 21 mars 2016 - 11:29:39
Document(s) archivé(s) le : mardi 11 avril 2017 - 11:54:23

Fichier

308.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Charles-Edmond Bichot. A new method, the fusion fission, for the relaxed k-way graph partitioning problem, and comparisons with some multilevel algorithms. Journal of Mathematical Modelling and Algorithms, Springer Verlag, 2007, 6 (3), pp 319-344. 〈10.1007/s10852-007-9059-4〉. 〈hal-01021583〉

Partager

Métriques

Consultations de la notice

59

Téléchargements de fichiers

75