Faster min-cut computation in unweighted hypergraphs/circuit netlists

摘要

A hypergraph minimum cut algorithm which is the fastest algorithm to date for computing a minimum cut in a weighted hypergraph was presented in W. K. Mak and D. F. Wong (2000). It is based on the repeated application of a special minimum s-t cut procedure. Unlike most minimum s-t cut procedures, it does not rely on any flow computation. And it runs in O(p + nlogn) time for a general weighted hypergraph where p is the total number of terminals of all hyperedges and n is the number of nodes in the input hypergraph. In this paper, we reduce its running time to O(p) if the input hypergraph is unweighted. Since a circuit netlist is an unweighted hypergraph where p = O(n) typically, this improvement can reduce the running time in circuit partitioning application significantly.