n-Level Graph Partitioning
n-Level Graph Partitioning
复制标题
n 级图划分
DOI：
10.1007/978-3-642-15775-2_24
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
P. Sanders
中科院分区：
文献类型：
--
作者：
Vitaly Osipov;P. Sanders
我们提出了一种基于极端思想的多层图划分算法，即在层次结构的每一层上只收缩一条边。这消除了对匹配算法的需要，并保证了非常好的划分质量，因为在两个级别之间几乎没有变化。使用高效的数据结构和新的灵活方法提前打破局部搜索改进，我们获得了一种算法，该算法可以扩展到大输入，并为许多输入产生最好的划分结果。例如，在Walshaw著名的基准表中，我们实现了155项改进，主宰了大型图的条目。
We present a multi-level graph partitioning algorithm based on the extreme idea to contract only a single edge on each level of the hierarchy. This obviates the need for a matching algorithm and promises very good partitioning quality since there are very few changes between two levels. Using an efficient data structure and new flexible ways to break local search improvements early, we obtain an algorithm that scales to large inputs and produces the best known partitioning results for many inputs. For example, in Walshaw's well known benchmark tables we achieve 155 improvements dominating the entries for large graphs.