Name
Abstract | ||
|---|---|---|
We develop a multilevel algorithm for hypergraph partitioning that contracts the vertices one at a time and thus allows very high quality. This includes a rating function that avoids nonuniform vertex weights, an efficient "semi-dynamic" hypergraph data structure, a very fast coarsening algorithm, and two new local search algorithms. One is a $k$-way hypergraph adaptation of Fiduccia-Mattheyses local search and gives high quality at reasonable cost. The other is an adaptation of size-constrained label propagation to hypergraphs. Comparisons with hMetis and PaToH indicate that the new algorithm yields better quality over several benchmark sets and has a running time that is comparable to hMetis. Using label propagation local search is several times faster than hMetis and gives better quality than PaToH for a VLSI benchmark set. |
Year | Venue | Field |
|---|---|---|
2015 | CoRR | Hypergraph partition,Data structure,Combinatorics,Vertex (geometry),Label propagation,Hypergraph,Constraint graph,Theoretical computer science,Local search (optimization),Very-large-scale integration,Mathematics |
DocType | Volume | Citations |
Journal | abs/1505.00693 | 2 |
PageRank | References | Authors |
0.37 | 22 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| vitali henne | 1 | 2 | 0.37 |
| Henning Meyerhenke | 2 | 522 | 42.22 |
| Peter Sanders | 3 | 36 | 2.43 |
| Sebastian Schlag | 4 | 38 | 5.18 |
| Christian Schulz | 5 | 46 | 2.99 |