A Parallel Implementation for Graph Partitioning Heuristics

LEONARDO ROGERIO, BINDA DA SILVA and RONEY, PIGNATON DA SILVA (2014) A Parallel Implementation for Graph Partitioning Heuristics. In: International Conference on Advances in Computing and Information Technology - ACIT 2014, 04-05 January, 2014, Bangkok.

[img]
Preview
Text
20140326_085715.pdf - Published Version

Download (492kB) | Preview
Official URL: https://www.seekdl.org/conferences/paper/details/2...

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.

Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: graph partitioning; parallel computing; grasp algorithms, heuristics
Depositing User: Mr. John Steve
Date Deposited: 10 May 2019 11:26
Last Modified: 10 May 2019 11:26
URI: http://publications.theired.org/id/eprint/2120

Actions (login required)

View Item View Item