Metaheuristics for graph bisection

• Published in: Proceedings of the 11th Annual conference on Genetic and evolutionary computation
• Main Author: Bichot, Charles-Edmond
• Other Authors: Extraction de Caractéristiques et Identification (imagine), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2009
• Subjects: [INFO]Computer Science [cs]; Canada; Metis
• Online Access: https://hal.science/hal-01437708; https://doi.org/10.1145/1569901.1570169

International audience This paper compares several metaheuristics on the balanced graph bisection problem and identifies their relative performance on structured test graphs. For this purpose, a Simple implementation of a graph Bisection Iterated Local Search algorithm (SBILS) is introduced. Its results are compared to the well-known Genetic Bisection Algorithm, to the state-of-the-art graph partitioning programs Metis and Scotch, and to the Fusion-Fission graph partitioning metaheuristic.