Geodesic
Optimization of a partitioning algorithm for a hypergraph with arbitrary weights of vertices
Numerical methods and programming, Tome 15 (2014) no. 3, pp. 400-410.

Voir la notice de l'article provenant de la source Math-Net.Ru

One of the methods for the decomposition of a large problem to subproblems is its representation as a graph or hypergraph and partition this graph to approximately equal subgraphs with minimal cuts. The balanced hypergraph partitioning with the minimization of the cut size reduces communication cost between decomposed subproblems. The well-known approach to the hypergraph decomposition is the Fiduccia–Mattheyses (FM) algorithm and its hierarchical modifications. In this paper we discuss a key data structure modifications of the FM-algorithm to improve the performance and quality of the hierarchical partitioning algorithms and to reduce the computational overheads during solving large problems by parallel methods.
Keywords: hypergraph partitioning, clustering, distributed computing systems, parallel programming.
Mots-clés : Fiduccia-Mattheyses algorithm 
@article{VMP_2014_15_3_a2,
     author = {A. S. Rusakov and M. V. Sheblaev},
     title = {Optimization of a partitioning algorithm for a hypergraph with arbitrary weights of vertices},
     journal = {Numerical methods and programming},
     pages = {400--410},
     publisher = {mathdoc},
     volume = {15},
     number = {3},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMP_2014_15_3_a2/}
}
TY  - JOUR
AU  - A. S. Rusakov
AU  - M. V. Sheblaev
TI  - Optimization of a partitioning algorithm for a hypergraph with arbitrary weights of vertices
JO  - Numerical methods and programming
PY  - 2014
SP  - 400
EP  - 410
VL  - 15
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VMP_2014_15_3_a2/
LA  - ru
ID  - VMP_2014_15_3_a2
ER  - 
%0 Journal Article
%A A. S. Rusakov
%A M. V. Sheblaev
%T Optimization of a partitioning algorithm for a hypergraph with arbitrary weights of vertices
%J Numerical methods and programming
%D 2014
%P 400-410
%V 15
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VMP_2014_15_3_a2/
%G ru
%F VMP_2014_15_3_a2
A. S. Rusakov; M. V. Sheblaev. Optimization of a partitioning algorithm for a hypergraph with arbitrary weights of vertices. Numerical methods and programming, Tome 15 (2014) no. 3, pp. 400-410. http://geodesic.mathdoc.fr/item/VMP_2014_15_3_a2/