An efficient memetic algorithm for the graph partitioning problem

• Banos, R., Gil, C., Montoya, F. G., & Ortega, J. (2004). A parallel multilevel metaheuristic for graph partitioning. Journal of Heuristics, 10, 315–336.

  Article  Google Scholar 

• Banos, R., Gil, C., Ortega, J., & Montoya, F. G. (2003). Multilevel heuristic algorithm for graph partitioning. In LNCS: Vol. 2611. Proceedings third European workshop on evolutionary computation in combinatorial optimization (pp. 143–153). Berlin: Springer.

  Google Scholar 

• Bichot, C.-E. (2006). A metaheuristic based on fusion and fission for partitioning problems. In 20th international parallel and distributed processing symposium (IPDPS) 2006.

  Google Scholar 

• Falkenauer, E. (1998). Genetic algorithms and grouping problems. New York: Wiley.

  Google Scholar 

• Fiduccia, C. M., & Mattheyses, R. M. (1982). Multilevel heuristic algorithm for graph partitioning. In 19th ACM/IEEE design automation conference (DAC) (pp. 175–181).

  Google Scholar 

• Galinier, P., & Hao, J.-K. (1999). Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization, 3, 379–397.

  Article  Google Scholar 

• Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of NP-completeness. San Francisco: Freeman.

  Google Scholar 

• Glass, C. A., & Prügel-Bennett, A. (2003). Genetic algorithm for graph colouring: exploration of Galinier and Hao’s algorithm. Journal of Combinatorial Optimization, 7, 229–236.

  Article  Google Scholar 

• Glover, F. (1989). Tabu search (part i). ORSA Journal on Computing, 1, 190–206.

  Google Scholar 

• Grefenstette, J. J. (1987). Incorporating problem specific knowledge in genetic algorithms. In Davis, L. (Ed.), Genetic algorithms and simulated annealing (pp. 42–60). San Mateo: Morgan Kaufmann.

  Google Scholar 

• Hendrickson, B., & Leland, R. (1995). A multilevel algorithm for partitioning graphs.

  Google Scholar 

• Hertz, A., & de Werra, D. (1987). Using tabu search techniques for graph coloring. Computing, 39, 345–351.

  Article  Google Scholar 

• Johnson, D. S., Aragon, C. R., McGeoch, L. A., & Shevon, C. (1991). Optimization by simulated annealing: an experimental evaluation; part ii, graph coloring and number partitioning. Operations Research, 39, 378–406.

  Article  Google Scholar 

• Karypis, G., & Kumar, V. (1996). Parallel multilevel k-way partitioning scheme for irregular graphs (Technical Report TR 96-036). Minneapolis: Dept. of Computer Science, University of Minnesota.

• Kernighan, B. W., & Lin, S. (1970). An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J., 49(2), 291–307.

  Google Scholar 

• Lang, K., & Rao, S. (2004). A flow-based method for improving the expansion or conductance of graph cuts. In LNCS: Vol. 2611. Integer programming and combinatorial optimization (pp. 325–337). Berlin: Springer.

  Chapter  Google Scholar 

• Meyerhenke, H., Monien, B., & Sauerwald, T. (2008). A new diffusion-based multilevel algorithm for computing graph partitions of very high quality. In Proc. 22nd IEEE intl. parallel and distributed processing symposium IPDPS’08.

  Google Scholar 

• Mühlenbein, H. (1992). Parallel genetic algorithm in combinatorial optimization. In Computer science and operations research (pp. 441–453).

  Google Scholar 

• Soper, A. J., Walshaw, C., & Cross, M. (2004). A combined evolutionary search and multilevel optimisation approach to graph partitioning. Journal of Global Optimization, 29(2), 225–241.

  Article  Google Scholar 

• Walshaw, C. (2004). Multilevel refinement for combinatorial optimisation problems. Annals of Operations Research, 131, 325–372.

  Article  Google Scholar 

• Walshaw, C., & Cross, M. (2000). Mesh partitioning: a multilevel balancing and refinement algorithm. SIAM J.Sci. Comput., 22(1), 63–80.

  Article  Google Scholar 

Download references