Charles-Edmond Bichot
ABSTRACT
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.
- C.-E. Bichot. A new meta-method for graph partitioning. In Proceedings of the 2008 IEEE Congress on Evolutionary Computation, pages 3498--3505, June 2008.Google Scholar
Cross Ref
- T. N. Bui and B. R. Moon. Genetic algorithm and graph partitioning. IEEE Trans. on Computers, 45(7):841--855, 1996. Google ScholarDigital Library
- G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 48(1):96--129, 1998. Google ScholarDigital Library
- H. R. Lorenco, O. Martin, and T. Stützle. Iterated local search. In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics. Kluwer, 2002.Google Scholar
- F. Pellegrini. SCOTCH 5.1 User's guide. ENSEIRB -- LaBRI, Université de Bordeaux I, 2008.Google Scholar
- T. Stützle. Iterated local search for the quadratic assignment problem. European Journal of Operational Research, 174(3):1519--1539, 2006.Google ScholarCross Ref
Index Terms
- Metaheuristics for graph bisection
Recommendations
Metaheuristics for large-scale instances of the linear ordering problem
ILS and GDA metaheuristics for the linear ordering problem are introduced.They are able to tackle large instances in line with real applications.Introduced methods are the first of their kind ever applied to large-sized instances.All best known ...
Subgraph extraction and metaheuristics for the maximum clique problem
The maximum clique problem involves finding the largest set of pairwise adjacent vertices in a graph. The problem is classic but still attracts much attention because of its hardness and its prominent applications. Our work is based on the existence of ...
Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem
Highlights- We study the Minimum Conductance Graph Partitioning Problem.
- We design an ...
AbstractThe minimum conductance graph partitioning problem (MC-GPP) is to partition the vertex set of a graph into two disjoint subsets while minimizing the ratio between the number of the edges crossing the two subsets and the smallest volume ...
Comments