Skip to Main content Skip to Navigation
New interface
Conference papers

A k-way Greedy Graph Partitioning with Initial Fixed Vertices for Parallel Applications

Abstract : Graph partitioning is used to solve the problem of distributing computations to a number of processors, in order to improve the performance of time consuming applications in parallel environments. A common approach to solve this problem is based on a multilevel framework, where the graph is firstly coarsened to a smaller instance and then it is partitioned in a number of parts using recursive bisection (RB) based methods. However, in applications where initial fixed vertices are used to model additional constraints of the problem, RB based methods often fail to produce partitions of good quality. In this paper, we propose a new direct k-way greedy graph growing algorithm, called KGGGP, that overcomes this issue and succeeds to produce partition with better quality than RB while respecting the constraint of fixed vertices. In the experimental section, we present results which compare KGGGP against state-of-the-art methods for graphs available from the popular DIMACS'10 collection.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Aurélien Esnard Connect in order to contact the contributor
Submitted on : Monday, February 22, 2016 - 7:12:34 PM
Last modification on : Saturday, June 25, 2022 - 7:44:18 PM
Long-term archiving on: : Sunday, November 13, 2016 - 12:49:37 AM


Files produced by the author(s)


  • HAL Id : hal-01277392, version 1



Maria Predari, Aurélien Esnard. A k-way Greedy Graph Partitioning with Initial Fixed Vertices for Parallel Applications. 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, Feb 2016, Heraklion, Greece. pp.8. ⟨hal-01277392⟩



Record views


Files downloads