Distributed Evolutionary Graph Partitioning
Distributed Evolutionary Graph Partitioning
复制标题
分布式进化图划分
DOI：
10.1137/1.9781611972924.2
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Christian Schulz
中科院分区：
文献类型：
--
作者：
P. Sanders;Christian Schulz
本文提出了一种新的分布式进化算法KaFFPaE来解决图划分问题，它利用了KaFFPa（Karlsruhe Fast Flow Partitioner）。使用我们的多级图划分KaFFPa提供了新的有效的交叉和变异算子。通过将这些与可扩展的通信协议相结合，我们获得了一个系统，该系统能够在很短的时间内改善许多输入的最佳已知划分结果。例如，在Walshaw的著名基准表中，我们能够改进或重新计算具有1%、3%和5%不平衡的表的76%的条目。
We present a novel distributed evolutionary algorithm, KaFFPaE, to solve the Graph Partitioning Problem, which makes use of KaFFPa (Karlsruhe Fast Flow Partitioner). The use of our multilevel graph partitioner KaFFPa provides new effective crossover and mutation operators. By combining these with a scalable communication protocol we obtain a system that is able to improve the best known partitioning results for many inputs in a very short amount of time. For example, in Walshaw's well known benchmark tables we are able to improve or recompute 76% of entries for the tables with 1%, 3% and 5% imbalance.