A parallelisable multi-level banded diffusion scheme for computing balanced partitions with smooth boundaries - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2007

A parallelisable multi-level banded diffusion scheme for computing balanced partitions with smooth boundaries

Résumé

Graph partitioning algorithms have yet to be improved, because graph-based local optimization algorithms do not compute smooth and globally-optimal frontiers, while global optimization algorithms are too expensive to be of practical use on large graphs. This paper presents a way to integrate a global optimization, diffusion algorithm in a banded multi-level framework, which dramatically reduces problem size while yielding balanced partitions with smooth boundaries. Since all of these algorithms do parallelize well, high-quality parallel graph partitioners built using these algorithms will have the same quality as state-of-the-art sequential partitioners
Fichier principal
Vignette du fichier
scotch_bipart_diffusion_europar_00.pdf (320.1 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00301427 , version 1 (21-07-2008)

Identifiants

Citer

François Pellegrini. A parallelisable multi-level banded diffusion scheme for computing balanced partitions with smooth boundaries. EuroPar, Aug 2007, Rennes, France. pp.195-204, ⟨10.1007/978-3-540-74466-5_22⟩. ⟨hal-00301427⟩
258 Consultations
165 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More