Multilevel k-way Hypergraph Partitioning

George Karypis and Vipin Kumar
VLSI Design, Vol. 11, No. 3, pp. 285 - 300, 2000
Download Paper
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.
Research topics: Circuit partitioning | hMETIS