优化了图割算法效率，可在超大规模图上快速求解最小割。
Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm
- 提出新算法fcBK，时间复杂度降至O(m|C|)。
- 支持千万级顶点、十亿级边的超大规模图处理。
- 内存高效，适合需要高性能图割的应用场景。
计算图中最小s-t割是解决众多计算机视觉问题的关键，常用方法为Boykov-Kolmogorov（BK）算法。本文从理论与实践双重视角重新审视该算法，将时间复杂度分析改进至O(mn|C|)，并提出更快更紧凑的fcBK算法，时间复杂度为O(m|C|)，其中m为边数，n为顶点数，|C|为割容量。此外，提出一种紧凑图表示方法，使实现能在128 GB内存机器上处理含超过10^9个顶点和10^10条边的图。在一系列基准数据集上的实验表明，本实现是当前最快可用的BK算法实现，凸显了内存效率的重要性。代码已公开，供后续研究使用。
原文摘要 · Abstract (English)
Computing a minimum $s$-$t$ cut in a graph is a solution to a wide range of computer vision problems, and is often done using the Boykov-Kolmogorov (BK) algorithm. In this paper, we revisit the BK algorithm from both a theoretical and practical point of view. We improve the analysis of the time complexity of the BK algorithm to $O(mn|C|)$ and propose a new algorithm, the fast and compact BK (fcBK) algorithm, with a time complexity of $O(m|C|)$, where $m$, $n$, and $|C|$ are the number of edges, number of vertices, and the capacity of the cut, respectively. We additionally propose a compact graph representation that allows our implementation to find a minimum $s$-$t$ cut in a graph with upwards of $10^9$ vertices and $10^{10}$ edges on a machine with 128 GB of memory. We find our implementation of the BK algorithm to be the fastest available implementation of the BK algorithm when evaluating on a comprehensive set of benchmark datasets, highlighting the importance of memory-efficient implementations. We make our implementations publicly available for further research and implementation development within minimum $s$-$t$ cut algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。