A new method, the fusion fission, for the relaxed k-way graph partitioning problem, and comparisons with some multilevel algorithms - ENAC - École nationale de l'aviation civile Accéder directement au contenu
Article Dans Une Revue Journal of Mathematical Modelling and Algorithms Année : 2007

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

Résumé

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.
Fichier principal
Vignette du fichier
308.pdf (1.01 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01021583 , version 1 (20-11-2014)

Identifiants

Citer

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, 2007, 6 (3), pp 319-344. ⟨10.1007/s10852-007-9059-4⟩. ⟨hal-01021583⟩
58 Consultations
310 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More