Moving Clusters within a Memetic Algorithm for Graph Partitioning

Inwook Hwang, Yong-Hyuk Kim and Yourim Yoon

Mathematical Problems in Engineering, 2015, vol. 2015, 1-10

Abstract:

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.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2015/238529.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2015/238529.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:238529

DOI: 10.1155/2015/238529

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().