A fast and robust network bisection algorithm

Partitioning is a fundamental problem in diverse fields of study such as pattern recognition, parallel processing, and the design of VLSI circuits. Recently, node clustering or compaction has been shown to enhance the performance of iterative partitioning algorithms by several authors. However, clustering has been mainly used as a preprocessing step before partitioning in existing methods. The paper describes a technique to extract clusters using information collected during a pass of an iterative exchange algorithm. Alternative approaches for the implementation of this new clustering technique are discussed, and one such approach is chosen to be incorporated in a modified Fiduccia-Mattheyses algorithm (C.M. Fiduccia, R.M. Mattheyses, 1982) based on a tradeoff between run time and performance. The resulting algorithm, BISECT, performs well in comparison with variants of the Kernighan-Lin algorithm including the Fiduccia-Mattheyses algorithm, local approaches, and simulated annealing on a wide variety of real and randomly generated benchmarks. BISECT is also used to find small vertex separators, and its results are compared with previous methods on several benchmarks. The empirical results show that BISECT is stable and is not very sensitive to the initial partition. Under suitably mild assumptions, BISECT can be shown to run in linear time. The empirical results confirm the speed of BISECT which can partition very large graphs (12,598 nodes and 91,961 edges) in less than six minutes of CPU time on a Sun Sparc 1+ workstation