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

Charles-Edmond Bichot (1)

1 ENAC - Ecole Nationale de l'Aviation Civile

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.

Mots clés: graph partitioning; multilevel; metaheuristics; fusion fission

Domaines: Mathématiques [math]; Optimisation et contrôle [math.OC]

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⟩