Novel multilevel particle swarm optimization algorithm for graph partitioning

Naresh Ghorpade, H. R. Bhapkar

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.

Full Text: PDF

Published: 2022-01-24

How to Cite this Article:

Naresh Ghorpade, H. R. Bhapkar, Novel multilevel particle swarm optimization algorithm for graph partitioning, J. Math. Comput. Sci., 12 (2022), Article ID 58

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.

 

Copyright ©2022 JMCS