Multilevel k-way Hypergraph Partitioning. Issue 3 (2000)

• Record Type: Journal Article
• Authors: Karypis, George; Kumar, Vipin
• Is Part Of: VLSI design. Volume 11:Issue 3(2000)
• Page Start: 285
• Page End: 300
• Publication Date: 2000
• Subjects: Circuit partitioning -- Physical design -- Placement -- Multilevel; Integrated circuits -- Very large scale integration -- Periodicals; 621.395
• DOI: 10.1155/2000/19436
• Languages: English
• ISSNs: 1065-514X

Abstract

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.