Network Flow-Based Refinement for Multilevel Hypergraph Partitioning
Network Flow-Based Refinement for Multilevel Hypergraph Partitioning
复制标题
基于网络流的多级超图分区细化
DOI：
10.1145/3329872
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Sebastian Schlag
中科院分区：
文献类型：
--
作者：
Tobias Heuer;P. Sanders;Sebastian Schlag
我们提出了用于多级超图形分区的改进框架，该框架使用块上使用最大流量计算来提高K道分区的解决方案质量。该框架将Karlsruhe快速流分区仪（KAFFPA）的基于流动的改进算法从图形到超图表进行了概括，并将其集成到HyperGraph分区器Karlsruhe HyperGraph Paph Praph分区（KAHYPAR）中。通过减少超图流网络的大小，改善KAFFPA中使用的流模型以及开发提高算法运行时间的技术，我们获得了一个分区器，该分区器为来自不同基准超图的最佳解决方案从不同的基准超图中用于不同的应用程序。连通性和切口度量的同时仍具有与HMETI相当的运行时间。在图形分区的情况下，即使通过改进的流动网络增强了后者，我们的算法也与KAFFPA进行了比较，与此同时，同时又超过了两个倍。最后，我们表明我们的算法提高了模因多级超图形分区师Kahypar-E的性能。
We present a refinement framework for multilevel hypergraph partitioning that uses max-flow computations on pairs of blocks to improve the solution quality of a k-way partition. The framework generalizes the flow-based improvement algorithm of the Karlsruhe Fast Flow Partitioner (KaFFPa) from graphs to hypergraphs and is integrated into the hypergraph partitioner Karlsruhe Hypergraph Partitioning (KaHyPar). By reducing the size of hypergraph flow networks, improving the flow model used in KaFFPa, and developing techniques to improve the running time of our algorithm, we obtain a partitioner that computes the best solutions for a wide range of benchmark hypergraphs from different application areas for both the connectivity and the cut-net metric while still having a running time comparable to that of hMetis. In the case of graph partitioning, our algorithm compares favorably with KaFFPa, even after enhancing the latter with our improved flow network, and at the same time is more than a factor of two faster. Finally, we show that our algorithm improves the performance of the memetic multilevel hypergraph partitioner KaHyPar-E.