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.
Type de document :
Communication dans un congrès
24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, Feb 2016, heraklion, Greece. pp.8, 2016, Parallel, Distributed, and Network-Based Processing (PDP 2016). 〈http://www.pdp2016.org〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01277392
Contributeur : Aurélien Esnard <>
Soumis le : lundi 22 février 2016 - 19:12:34
Dernière modification le : jeudi 11 janvier 2018 - 06:22:35
Document(s) archivé(s) le : dimanche 13 novembre 2016 - 00:49:37

Fichier

conf15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01277392, version 1

Collections

Citation

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, 2016, Parallel, Distributed, and Network-Based Processing (PDP 2016). 〈http://www.pdp2016.org〉. 〈hal-01277392〉

Partager

Métriques

Consultations de la notice

356

Téléchargements de fichiers

370