# Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer Vision

arXiv: https://arxiv.org/abs/2202.00418 · HTML: https://mlsanity.com/paper/2202.00418/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 113 references that are in the map.
- First posted on arXiv 1 Feb 2022.

## Builds on (most cited first, 17 of 17)

- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [V-Net: Fully Convolutional Neural Networks for Volumetric Medical Image Segmentation](https://mlsanity.com/paper/1606.04797/) (2016)
- [3D U-Net: Learning Dense Volumetric Segmentation from Sparse Annotation](https://mlsanity.com/paper/1606.06650/) (2016)
- [Image Segmentation Using Deep Learning: A Survey](https://mlsanity.com/paper/2001.05566/) (2020)
- [A large annotated medical image dataset for the development and evaluation of segmentation algorithms](https://mlsanity.com/paper/1902.09063/) (2019)
- [Embracing Imperfect Datasets: A Review of Deep Learning Solutions for Medical Image Segmentation](https://mlsanity.com/paper/1908.10454/) (2019)
- [Simple Does It: Weakly Supervised Instance and Semantic Segmentation](https://mlsanity.com/paper/1603.07485/) (2016)
- [Deep Snake for Real-Time Instance Segmentation](https://mlsanity.com/paper/2001.01629/) (2020)
- [Voxel2Mesh: 3D Mesh Model Generation from Volumetric Data](https://mlsanity.com/paper/1912.03681/) (2019)
- [A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching](https://mlsanity.com/paper/1612.05476/) (2016)
- [A Comparative Study of Modern Inference Techniques for Structured Discrete Energy Minimization Problems](https://mlsanity.com/paper/1404.0533/) (2014)
- [Fusion Moves for Graph Matching](https://mlsanity.com/paper/2101.12085/) (2021)
- [Deep LOGISMOS: Deep Learning Graph-based 3D Segmentation of Pancreatic Tumors on CT scans](https://mlsanity.com/paper/1801.08599/) (2018)
- [Efficient optimization for Hierarchically-structured Interacting Segments (HINTS)](https://mlsanity.com/paper/1703.10530/) (2017)
- [Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm](https://mlsanity.com/paper/1507.01926/) (2015)
- [Dynamic Parallel and Distributed Graph Cuts](https://mlsanity.com/paper/1512.00101/) (2015)

## Built on by (most cited first, 2 of 2)

- [gcDLSeg: Integrating Graph-cut into Deep Learning for Binary Semantic Segmentation](https://mlsanity.com/paper/2312.04713/) (2023)
- [Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm](https://mlsanity.com/paper/2605.13402/) (2026)

## Abstract (arXiv)

Minimum cut/maximum flow (min-cut/max-flow) algorithms solve a variety of problems in computer vision and thus significant effort has been put into developing fast min-cut/max-flow algorithms. As a result, it is difficult to choose an ideal algorithm for a given problem. Furthermore, parallel algorithms have not been thoroughly compared. In this paper, we evaluate the state-of-the-art serial and parallel min-cut/max-flow algorithms on the largest set of computer vision problems yet. We focus on generic algorithms, i.e., for unstructured graphs, but also compare with the specialized GridCut implementation. When applicable, GridCut performs best. Otherwise, the two pseudoflow algorithms, Hochbaum pseudoflow and excesses incremental breadth first search, achieves the overall best performance. The most memory efficient implementation tested is the Boykov-Kolmogorov algorithm. Amongst generic parallel algorithms, we find the bottom-up merging approach by Liu and Sun to be best, but no method is dominant. Of the generic parallel methods, only the parallel preflow push-relabel algorithm is able to efficiently scale with many processors across problem sizes, and no generic parallel method consistently outperforms serial algorithms. Finally, we provide and evaluate strategies for algorithm selection to obtain good expected performance. We make our dataset and implementations publicly available for further research.