Volume 3 Number 2 (Mar. 2014)
Home > Archive > 2014 > Volume 3 Number 2 (Mar. 2014) >
IJCCE 2014 Vol.3(2): 87-92 ISSN: 2010-3743
DOI: 10.7763/IJCCE.2014.V3.297

Applying a Parallel Solution to the Graph Partitioning Problem in the Simulation of Multiphase Flows

Roney Pignaton da Silva, Leonardo Rogério Binda da Silva, and Luís Otávio Rigo Junior
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.

General Information

ISSN: 2010-3743 (Online)
Abbreviated Title: Int. J. Comput. Commun. Eng.
Frequency: Quarterly
Editor-in-Chief: Dr. Maode Ma
Abstracting/ Indexing: INSPEC, Google Scholar, Crossref, EBSCO, ProQuest, and Electronic Journals Library
E-mail: ijcce@iap.org
  • Jun 20, 2019 News!

    IJCCE Vol. 6, No. 3 - Vol. 7, No. 3 have been indexed by EI (Inspec) Inspec, created by the Institution of Engineering and Tech.!   [Click]

  • Jun 10, 2021 News!

    IJCCE Vol.10, No.3 is published with online version!   [Click]

  • Mar 12, 2021 News!

    IJCCE Vol.10, No.2 is published with online version!   [Click]

  • Dec 09, 2020 News!

    IJCCE Vol.10, No.1 is published with online version!   [Click]

  • Sep 23, 2020 News!

    IJCCE Vol.9, No.4 is published with online version!   [Click]

  • Read more>>