Novel multilevel particle swarm optimization algorithm for graph partitioning
Abstract
Graph partitioning is crucial step in resolving real time applications in the field of image analysis, smart city designing, wireless communications, data analysis etc. Though considerable research has been done for getting an optimal partitioning of graphs still it demands enhancement for diverse application problems. Hybrid graph partitioning approaches are promising and possess ability to partition graphs with large number of vertices. In our research we have developed multilevel particle swarm optimization algorithm for graph partitioning. Size of the graph is reduced by heavy edge matching algorithm and then greedy graph growing partitioning is used to divide the graph. Discrete particle swarm optimization used at the most important stage of refinement. Performance is evaluated by using Walshaw’s Benchmark graphs and from analysis it has been observed that proposed algorithm generates optimal partitioning with reduced cut values and computational cost.
Copyright © 2022 Naresh Ghorpade, H. R. Bhapkar. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Cite this article
N. Ghorpade, H. R. Bhapkar, Novel multilevel particle swarm optimization algorithm for graph partitioning, J. Math. Comput. Sci. 12 (2022), 58. https://doi.org/10.28919/jmcs/6917
BibTeX
@article{Ghorpade2022,
author = {Ghorpade, Naresh and Bhapkar, H. R.},
title = {Novel multilevel particle swarm optimization algorithm for graph partitioning},
journal = {J. Math. Comput. Sci.},
volume = {12},
year = {2022},
pages = {58},
doi = {10.28919/jmcs/6917}
}