Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-enac.archives-ouvertes.fr/hal-01021583
Contributor : Laurence Porte <>
Submitted on : Thursday, November 20, 2014 - 4:08:31 PM
Last modification on : Monday, December 10, 2018 - 5:55:13 PM
Document(s) archivé(s) le : Tuesday, April 11, 2017 - 11:54:23 AM

File

308.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

158

Files downloads

274