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...
Published in: | Proceedings of the 11th Annual conference on Genetic and evolutionary computation |
---|---|
Main Author: | |
Other Authors: | , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2009
|
Subjects: | |
Online Access: | https://hal.science/hal-01437708 https://doi.org/10.1145/1569901.1570169 |
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. |
---|