论文标题
在实践中找到所有全球最小削减
Finding All Global Minimum Cuts In Practice
论文作者
论文摘要
我们提出了一种实际上有效的算法，该算法在巨大的无向图中找到了所有全球最小削减。我们的算法使用多种内核化规则将图形减少到一个小型实例，然后使用Nagamochi，Nakao和Ibaraki的算法的优化版本找到所有最小切割。在共享内存中，我们能够在几分钟内找到所有最小图表的所有最小剪切图。我们还提供了一种新的线性时间算法，以找到输入所有最小切割的表示最低的最小切割。
We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using an optimized version of the algorithm of Nagamochi, Nakao and Ibaraki. In shared memory we are able to find all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes. We also give a new linear time algorithm to find the most balanced minimum cuts given as input the representation of all minimum cuts.
