Optimization of a partitioning algorithm for a hypergraph with arbitrary weights of vertices
A. S. Rusakov, M. V. Sheblaev
Institute for Design Problems in Microelectronics of Russian Academy of Sciences, Moscow
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.
hypergraph partitioning, Fiduccia-Mattheyses algorithm, clustering, distributed computing systems, parallel programming.
PDF file (235 kB)
519.658; 519.677; 519.176
A. S. Rusakov, M. V. Sheblaev, “Optimization of a partitioning algorithm for a hypergraph with arbitrary weights of vertices”, Num. Meth. Prog., 15:3 (2014), 400–410
Citation in format AMSBIB
\by A.~S.~Rusakov, M.~V.~Sheblaev
\paper Optimization of a partitioning algorithm for a hypergraph with arbitrary weights of vertices
\jour Num. Meth. Prog.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|