Multilevel k-way Hypergraph Partitioning

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1999
Accession Number
AD1020024

Entities

People

  • George Karypis
  • Vipin Kumar

Organizations

  • University of Minnesota

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Cell Movement
  • Cells
  • Climbing
  • Computer Science
  • Computers
  • Data Mining
  • Electronic Mail
  • High Performance Computing
  • Iterations
  • Military Research
  • Minnesota
  • Sequences
  • Supercomputers

Fields of Study

  • Computer science

Readers

  • Computational Fluid Dynamics (CFD)
  • Neural Network Machine Learning.