Title :
A fast hypergraph minimum cut algorithm
Author :
Mak, Wai-Kei ; Wong, D.E.
Author_Institution :
Dept. of Comput. Sci. & Eng., Univ. of South Florida, Tampa, FL, USA
Abstract :
We present the fastest algorithm known today for computing a global minimum cut in a hypergraph. Unlike most minimum cut algorithms which rely on flow computations in a network, ours is a non-flow based algorithm. Since the netlist of a circuit can be modelled naturally as a hypergraph, this opens the opportunity for finding very high quality solutions for the circuit partitioning problem
Keywords :
VLSI; circuit layout CAD; computational complexity; graph theory; integrated circuit layout; network topology; VLSI layout; circuit netlist modelling; circuit partitioning problem; fast hypergraph minimum cut algorithm; global minimum cut; nonflow based algorithm; Computer networks; Computer science; Costs; Delay; Integrated circuit interconnections; Joining processes; Particle separators; Partitioning algorithms; System-on-a-chip; Very large scale integration;
Conference_Titel :
Circuits and Systems, 1999. ISCAS '99. Proceedings of the 1999 IEEE International Symposium on
Conference_Location :
Orlando, FL
Print_ISBN :
0-7803-5471-0
DOI :
10.1109/ISCAS.1999.780122
