A fast hypergraph min-cut algorithm for circuit partitioning

Circuit partitioning is one of the central problems in VLSI system design. The primary objective of circuit partitioning is to minimize the number of interconnections between different components of the partitioned circuit. S o the circuit partitioning problem is closely related to the minimum cut pr oblem. Recently, two very fast algorithms for computing minimum cuts in gra phs were reported (Nagamochi and Ibaraki; SIAM J. Discrete Math. 5 (1) (199 2) 54; Steer and Wagner, J. ACM 44(4) (1997) 585). However, it is known tha t a circuit netlist cannot be accurately modeled by a graph, but only by a hypergraph. In this paper, we present the fastest algorithm known today for computing a minimum cut in a hypergraph which is a non-trivial extension o f the result in Steer and Wagner (J. ACM 44(4) (1997) 586). Since the netli st of a circuit can be modeled naturally as a hypergraph, this opens the op portunity for finding very-high-quality solutions for the circuit partition ing problem. Unlike most minimum cut algorithms which rely on flow computat ions in a network, ours is a non-flow-based algorithm. (C) 2000 Elsevier Sc ience B.V, All rights reserved.