Abstract: “The Graph Partitioning Problem (GPP) has several practical applications in many areas, such as design of VLSI ( Very-large-scale integration) circuits, solution of numerical methods for simulation problems that include factorization of sparse matrix and partitioning of finite elements meshes for parallel programming applications, between others. The GPP tends to be NP-hard and optimal solutions for solving them are infeasible when the number of vertices of the graph is very large. There has been an increased used of heuristic and metaheuristic algorithms to solve the PPG to get good results where exceptional results are not obtainable by practical means. This article proposes an efficient parallel solution to the GPP problem based on the implementation of existing heuristics in a computational cluster. The proposed solution improves the execution time and, by introducing some random features into the original heuristics, improve the quality of the created partitions.”

Keywords: graph partitioning; parallel computing; grasp algorithms, heuristics