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 meshes of finite elements 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. Tests are applied to the simulation of multiphase flows in porous media to oil recovery in order to create partitions to be distributed along computational nodes in a cluster.

Index Terms—Graph partitioning, parallel computing, grasp algorithms, heuristics, multiphase flow.

The authors are with the Federal University of Espirito Santo, Brazil (e-mail: roney.silva@ufes.br).

Cite:Roney Pignaton da Silva, Leonardo Rogério Binda da Silva, and Luís Otávio Rigo Junior, "Applying a Parallel Solution to the Graph Partitioning Problem in the Simulation of Multiphase Flows," International Journal of Computer and Communication Engineering vol. 3, no. 2, pp. 87-92, 2014.