NUK - logo
E-viri
Celotno besedilo
  • Hybrid spectral/iterative p...
    Zien, Jason Y; Chan, Pak K; Schlag, Martine

    1997 Proceedings of IEEE International Conference on Computer Aided Design (ICCAD), 1997
    Conference Proceeding, Journal Article

    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 ML/sub F/ for 4-way partitions.