Faster min-cut computation in unweighted hypergraphs/circuit netlists

[[abstract]]A novel hypergraph minimum cut algorithm which is the fastest algorithm to date for computing a minimum cut in a weighted hypergraph was presented in [8]. 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 0(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. © 2005 IEEE.[[fileno]]2030233030004[[department]]資訊工程學