Multilevel k-way hypergraph partitioning

Research output: Contribution to journalConference articlepeer-review

290 Scopus citations

Abstract

In this paper, we present a new multilevel k-way hypergraph partitioning algorithm that substantially outperforms the existing state-of-the-art K-PM/LR algorithm for multi-way partitioning, both for optimizing local as well as global objectives. Experiments on the ISPD98 benchmark suite show that the partitionings produced by our scheme are on the average 15% to 23% better than those produced by the K-PM/LR algorithm, both in terms of the hyperedge cut as well as the (K-1) metric. Furthermore, our algorithm is significantly faster, requiring 4 to 5 times less time than that required by K-PM/LR.

Original languageEnglish (US)
Pages (from-to)343-348
Number of pages6
JournalProceedings - Design Automation Conference
DOIs
StatePublished - 1999
EventProceedings of the 1999 36th Annual Design Automation Conference (DAC) - New Orleans, LA, USA
Duration: Jun 21 1999Jun 25 1999

Fingerprint Dive into the research topics of 'Multilevel k-way hypergraph partitioning'. Together they form a unique fingerprint.

Cite this