Post-analysis-based clustering dramatically improves theFiduccia-Mattheyses algorithm

摘要

This paper describes a new partitioning algorithm, BISECT, whichnis an extension of the Fiduccia-Mattheyses (FM) algorithm thatnrecursively combines clustering and iterative improvement. A postnanalysis of sequences of moves in one pass generates disjoint subsets ofnnodes for clustering. After clustering BISECT is applied again on thencompacted circuit. BISECT is stabler, achieves results that can be up ton73 times better than FM, and runs in linear time under suitably mildnassumptions. BISECT also performs well in comparison with thenKernighan-Lin algorithm and simulated annealing. The empirical resultsnshow that BISECT is stable and is not very sensitive to the initialnpartition. For many random sparse graphs, BISECT achieves 0-cutnbisections (balanced partitions)