Multilevel hypergraph partitioning
George Karypis, Rajat Aggarwal, Vipin Kumar et al. · Proceedings - ACM IEEE Design Automation Conference · 1997
In this paper, we present a new hypergraph partitioning algorithmthat is based on the multilevel paradigm. In the multilevel paradigm,a sequence of successively coarser hypergraphs is constructed. Abisection of the smallest hypergraph is computed and it is used toobtain a bisection of the original hypergraph by successively projectingand refining the bisection to the next level finer hypergraph.We evaluate the performance both in terms of the size of the hyper-edgecut on the bisection as well as run time on a number of VLSIcircuits. Our experiments show that our multilevel hypergraph partitioningalgorithm produces high quality partitioning in relativelysmall amount of time. The quality of the partitionings produced byour scheme are on the average 4% to 23% better than those producedby other state-of-the-art schemes. Furthermore, our partitioning algorithmissignificantly faster, often requiring 4 to 15 times less timethan that required by the other schemes. Our multilevel hypergraphpartitioning algorithm scales very well for large hypergraphs. Hypergraphswith over 100,000 vertices can be bisected in a few minuteson today's workstations. Also, on the large hypergraphs, ourscheme outperforms other schemes (in hyperedge cut) quite consistentlywith larger margins (9% to 30%).
Cited by 715 works. doi:10.1145/266021.266273 Open-access PDF
Authors
References
- An Efficient Heuristic Procedure for Partitioning Graphs
- Graphs and Hypergraphs
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- Partitioning Sparse Matrices with Eigenvectors of Graphs
- Combinatorial Optimization
- A proper model for the partitioning of electrical circuits
- A multilevel algorithm for partitioning graphs
- An Improved Min-Cut Algonthm for Partitioning VLSI Networks
- Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems
- Recent directions in netlist partitioning: a survey