Numerical methods and programming
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Num. Meth. Prog.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Num. Meth. Prog., 2014, Volume 15, Issue 3, Pages 400–410 (Mi vmp259)  

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

Abstract: 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, Fiduccia-Mattheyses algorithm, clustering, distributed computing systems, parallel programming.

Full text: PDF file (235 kB)
UDC: 519.658; 519.677; 519.176
Received: 02.06.2014

Citation: 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
\Bibitem{RusShe14}
\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.
\yr 2014
\vol 15
\issue 3
\pages 400--410
\mathnet{http://mi.mathnet.ru/vmp259}


Linking options:
  • http://mi.mathnet.ru/eng/vmp259
  • http://mi.mathnet.ru/eng/vmp/v15/i3/p400

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Numerical methods and programming
    Number of views:
    This page:172
    Full text:72

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022