TY - JOUR

T1 - A fast hypergraph min-cut algorithm for circuit partitioning

AU - Mak, Wai-Kei

AU - Wong, D. F.

N1 - The work of this author was partially supported by the National Science Foundation under grant CCR-9912390 and by the Texas Advanced Research Program under Grant No. 003658288.

PY - 2000/11

Y1 - 2000/11

N2 - 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. So the circuit partitioning problem is closely related to the minimum cut problem. Recently, two very fast algorithms for computing minimum cuts in graphs were reported. However, it is known that 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 of the result in Stoer and Wagner. Since the netlist of a circuit can be modeled naturally as a hypergraph, this opens the opportunity for finding very-high-quality solutions for the circuit partitioning problem. Unlike most minimum cut algorithms which rely on flow computations in a network, ours is a non-flow-based algorithm.

AB - 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. So the circuit partitioning problem is closely related to the minimum cut problem. Recently, two very fast algorithms for computing minimum cuts in graphs were reported. However, it is known that 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 of the result in Stoer and Wagner. Since the netlist of a circuit can be modeled naturally as a hypergraph, this opens the opportunity for finding very-high-quality solutions for the circuit partitioning problem. Unlike most minimum cut algorithms which rely on flow computations in a network, ours is a non-flow-based algorithm.

UR - http://www.scopus.com/inward/record.url?scp=0034427497&partnerID=8YFLogxK

U2 - 10.1016/S0167-9260(00)00008-0

DO - 10.1016/S0167-9260(00)00008-0

M3 - Journal article

AN - SCOPUS:0034427497

SN - 0167-9260

VL - 30

SP - 1

EP - 11

JO - Integration, the VLSI Journal

JF - Integration, the VLSI Journal

IS - 1

ER -