https://hal-enac.archives-ouvertes.fr/hal-01021583Bichot, Charles-EdmondCharles-EdmondBichotENAC - Ecole Nationale de l'Aviation CivileA new method, the fusion fission, for the relaxed k-way graph partitioning problem, and comparisons with some multilevel algorithmsHAL CCSD2007graph partitioningmultilevelmetaheuristicsfusion fission[MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC]Porte, Laurence2014-11-20 16:08:312021-10-19 11:02:492014-11-20 16:10:16enJournal articleshttps://hal-enac.archives-ouvertes.fr/hal-01021583/document10.1007/s10852-007-9059-4application/pdf1In 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.