2021/01/01 by Lars Gottesbüren, Gottesbüren, Lars, Michael Hamann +1
Computer Science · Engineering · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Interconnection Networks and Systems #Parallel #VLSI and FPGA Design Techniques #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2112.12704
openalex publication_date 2021/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Balanced hypergraph partitioning is a classical NP-hard optimization problem with applications in various domains such as VLSI design, simulating quantum circuits, optimizing data placement in distributed databases or minimizing communication volume in high-performance computing. Engineering parallel heuristics for this problem is a topic of recent research. Most of them are non-deterministic though. In this work, we design and implement a highly scalable deterministic algorithm in the state-of-the-art parallel partitioning framework Mt-KaHyPar. On our extensive set of benchmark instances, it achieves similar partition quality and performance as a comparable but non-deterministic configuration of Mt-KaHyPar and outperforms the only other existing parallel deterministic algorithm BiPart regarding partition quality, running time and parallel speedups.