Metaheuristics for graph bisection

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 res...

Full description

Bibliographic Details
Published in:Proceedings of the 11th Annual conference on Genetic and evolutionary computation - GECCO '09
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), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2)
Format: Conference Object
Language:English
Published: HAL CCSD 2009
Subjects:
[INFO]Computer Science [cs]
Canada
Metis
Online Access:https://hal.archives-ouvertes.fr/hal-01437708
https://doi.org/10.1145/1569901.1570169
Description
Summary: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.

Similar Items