Multilevelk-way Hypergraph Partitioning

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

[学科分类] 电子、光学、磁材料