About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
ICCAD 1997
Conference paper
Hybrid spectral/iterative partitioning
Abstract
We develop a new multi-way, hybrid spectral/iterative hypergraph partitioning algorithm that combines the strengths of spectral partitioners and iterative improvement algorithms to create a new class of partitioners. We use spectral information (the eigenvectors of a graph) to generate initial partitions, influence the selection of iterative improvement moves, and break out of local minima. Our 3-way and 4-way partitioning results exhibit significant improvement over current published results, demonstrating the effectiveness of our new method. Our hybrid algorithm produces an improvement of 25% over GFM for 3-way partitions, 41% improvement over GFM for 4-way partitions, and 58% improvement over MLF for 4-way partitions.