2000/01/01 by Chris Walshaw, M. Cross · 183 citations
Computer Science · Engineering · Mathematics · #Algorithm #Computer science #Graph #Graph partition #Interconnection Networks and Systems #Load balancing (electrical power) #Low-power high-performance VLSI design #Mathematical optimization #Mathematics #Partition (number theory) #Polygon mesh #Theoretical computer science #VLSI and FPGA Design Techniques
paper · doi:10.1137/s1064827598337373
published in SIAM Journal on Scientific Computing 22(1), 63-80 (Society for Industrial and Applied Mathematics)
openalex publication_date 2000/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
Multilevel algorithms are a successful class of optimization techniques which addresses the mesh partitioning problem. They usually combine a graph contraction algorithm together with a local optimization method which refines the partition at each graph level. In this paper we present an enhancement of the technique which uses imbalance to achieve higher quality partitions. We also present a formulation of the Kernighan--Lin partition optimization algorithm which incorporates load-balancing. The resulting algorithm is tested against a different but related state-of-the-art partitioner and shown to provide improved results.