Moving clusters within a memetic algorithm for graph partitioning

DOI10.1155/2015/238529MaRDI QIDQ1665049zbMATH OpenOpenAlexWikidataFDO

Authors Inwook Hwang, Yong-Hyuk Kim, Yourim Yoon

Publication date 27 August 2018

Published in Mathematical Problems in Engineering (Search for Journal in Brave)

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.1155/2015/238529

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

Summary: Most memetic algorithms (MAs) for graph partitioning reduce the cut size of partitions using iterative improvement. But this local process considers one vertex at a time and fails to move clusters between subsets when the movement of any single vertex increases cut size, even though moving the whole cluster would reduce it. A new heuristic identifies clusters from the population of locally optimized random partitions that must anyway be created to seed the MA, and as the MA runs it makes beneficial cluster moves. Results on standard benchmark graphs show significant reductions in cut size, in some cases improving on the best result in the literature.

Recommendations

• An efficient memetic algorithm for the graph partitioning problem
• Memetic graph clustering
• A grid-cluster framework for memetic algorithms
• A genetic algorithm for graph partitioning
• Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
• A combined evolutionary search and multilevel optimisation approach to graph-partitioning
• (Semi-)External Algorithms for Graph Partitioning and Clustering

Cites work

• A combined evolutionary search and multilevel optimisation approach to graph-partitioning
• A theoretical and empirical study on unbiased boundary-extended crossover for real-valued representation
• An Efficient Heuristic Procedure for Partitioning Graphs
• An Improved Min-Cut Algonthm for Partitioning VLSI Networks
• Evolutionary optimization and the estimation of search distributions with applications to graph bipartitioning.
• Finding good approximate vertex and edge partitions is NP-hard
• Genetic algorithm and graph partitioning
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2013539 (Why is no real title available?)
• scientific article; zbMATH DE number 2013560 (Why is no real title available?)
• Lock-gain based graph partitioning
• Multiple-way network partitioning
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• Quotient geometric crossovers and redundant encodings
• Tabu search for graph partitioning

Cited in

(3)

• A reactive self-tuning scheme for multilevel graph partitioning
• Memetic graph clustering
• An efficient memetic algorithm for the graph partitioning problem

This page was built for publication: Moving clusters within a memetic algorithm for graph partitioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1665049)