Fast hypergraph partition
- 1 January 1989
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 762-766
- https://doi.org/10.1145/74382.74524
Abstract
We present a new &Ogr;(n2) heuristic for hypergraph min-cut bipartitioning, an important problem in circuit placement. Fastest previous methods for this problem are &Ogr;(n2 log n). Our approach is based on the intersection graph G dual to the input hypergraph. Paths in G are used to construct partial bipartitions which can be completed optimally. The method is provably good and, in particular, obtains optimum results for “difficult” inputs, i.e., hypergraphs with smaller than expected minimum cutsize. Computational results for a wide range of inputs are also discussed.This publication has 0 references indexed in Scilit: