pith. machine review for the scientific record. sign in

arxiv: 2605.13402 · v1 · submitted 2026-05-13 · 💻 cs.CV · cs.DS

Recognition: no theorem link

Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm

Christian M{\o}ller Mikkelstrup , Anders Bjorholm Dahl , Philip Bille , Vedrana Andersen Dahl , Inge Li G{\o}rtz
Authors on Pith no claims yet

Pith reviewed 2026-05-14 20:41 UTC · model grok-4.3

classification 💻 cs.CV cs.DS
keywords Boykov-Kolmogorov algorithmminimum s-t cutgraph cutsmaximum flowcomputer visioncompact data structuresefficient implementation
0
0 comments X

The pith

The fcBK algorithm computes minimum s-t cuts in O(m|C|) time using a compact graph representation for graphs with billions of vertices.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper first sharpens the theoretical bound on the original Boykov-Kolmogorov algorithm to O(mn|C|) time. It then introduces the fast and compact BK variant, fcBK, that lowers the bound to O(m|C|). A memory-compact graph encoding is added so that the same algorithm can store and process networks containing 10^9 vertices and 10^10 edges inside 128 GB of RAM. These changes matter because minimum s-t cuts are the engine behind many computer-vision tasks, yet prior implementations either ran too slowly or ran out of memory on high-resolution or volumetric data. The authors also release code that outperforms other BK implementations on standard benchmark suites.

Core claim

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.

What carries the argument

The fcBK algorithm paired with its compact graph representation, which stores the flow network in a memory-efficient form while preserving the correctness of the underlying push-relabel operations.

If this is right

  • The original BK algorithm is shown to run in O(mn|C|) time rather than a tighter bound previously assumed.
  • fcBK makes minimum-cut computation scale linearly with cut capacity instead of with the product of vertices and cut capacity.
  • Graphs an order of magnitude larger than before become solvable on ordinary workstations with 128 GB RAM.
  • The released implementation runs faster than prior BK codes on a wide range of computer-vision benchmark graphs.
  • Public code release allows direct comparison and further engineering of minimum-cut solvers.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • When cut capacities remain small relative to graph size, as is common in segmentation, the new bound implies near-linear practical running times.
  • Similar compact encodings could be applied to other max-flow algorithms to reach comparable scale on commodity hardware.
  • The method opens the door to processing full-resolution 3-D medical volumes or high-frame-rate video without aggressive downsampling.
  • Benchmark results suggest that memory locality, not just asymptotic time, is now the dominant factor in practical min-cut speed.

Load-bearing premise

The compact graph representation preserves the correctness of the minimum-cut computation and incurs no hidden asymptotic overhead on the claimed time bound.

What would settle it

A graph with 10^9 vertices on which fcBK either exceeds O(m|C|) operations, uses more than the stated memory, or returns a cut whose capacity is not minimal.

Figures

Figures reproduced from arXiv: 2605.13402 by Anders Bjorholm Dahl, Christian M{\o}ller Mikkelstrup, Inge Li G{\o}rtz, Philip Bille, Vedrana Andersen Dahl.

Figure 1
Figure 1. Figure 1: Example describing the notation. (a) A graph [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Example state of the BK algorithm after the augmentation stage. Edges [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Example layout of the interleaved list in our compact representation [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Bar chart visualizing the average performance of each implementation when measuring the solve time, total time, or memory usage. Each bar averages [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Scatterplot visualizing the performance of each implementation across datasets. Each point maps the solve time and memory usage of an implementation [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Visualizations of single and multiple surface detection in large volumes. (a) Visualization of the eye of a bumblebee (top left). We use [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript improves the time-complexity analysis of the Boykov-Kolmogorov (BK) algorithm to O(mn|C|), introduces the fast-and-compact BK (fcBK) variant claimed to run in O(m|C|), presents a compact graph representation that enables min s-t cuts on instances with 10^9 vertices and 10^10 edges within 128 GB RAM, and reports that the resulting implementation is the fastest among available BK codes on a suite of benchmark datasets, with source code released publicly.

Significance. If the O(m|C|) bound is rigorously established and the compact representation incurs no hidden asymptotic overhead, the work would be significant for large-scale computer-vision pipelines that rely on graph cuts; the combination of a tightened theoretical bound, memory-efficient scaling to billion-vertex graphs, and reproducible public code constitutes a concrete practical contribution.

major comments (2)
  1. [§3] §3 (Complexity Analysis of fcBK): the O(m|C|) claim rests on the unstated invariant that every neighbor iteration and capacity lookup in the compact representation remains amortized O(1) throughout the |C|-bounded augmentations; the manuscript does not exhibit the concrete data structures (array-based adjacency, hash tables, etc.) nor prove that the two-tree growth and orphan-adoption phases avoid logarithmic or linear-in-n factors when n reaches 10^9.
  2. [§5] §5 (Experimental Evaluation): the claim that the implementation is the fastest available BK code is load-bearing for the practical contribution, yet the reported timings do not isolate the contribution of the compact representation versus low-level tuning; in particular, memory-footprint and cache-miss statistics for the largest graphs are not provided, leaving open whether the observed speed-ups are consistent with the removal of the n factor.
minor comments (2)
  1. [Abstract] Abstract and §2: the baseline complexity stated for the original BK algorithm should be made explicit (commonly O(mn^2|C|)) so that the improvement to O(mn|C|) is immediately comparable.
  2. Notation: |C| is used both for cut capacity and (implicitly) for the number of augmentations; a single sentence clarifying the relationship would remove ambiguity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed feedback. We address each major comment below and have revised the manuscript accordingly to strengthen the presentation of both the theoretical analysis and the experimental results.

read point-by-point responses

  1. Referee: [§3] §3 (Complexity Analysis of fcBK): the O(m|C|) claim rests on the unstated invariant that every neighbor iteration and capacity lookup in the compact representation remains amortized O(1) throughout the |C|-bounded augmentations; the manuscript does not exhibit the concrete data structures (array-based adjacency, hash tables, etc.) nor prove that the two-tree growth and orphan-adoption phases avoid logarithmic or linear-in-n factors when n reaches 10^9.

    Authors: We agree that the original submission left the data-structure details and the amortized-O(1) invariant implicit. In the revised manuscript we have expanded §3 with an explicit description of the compact representation (array-based adjacency lists with direct indexing for neighbor iteration and a hash table for capacity queries). We now prove that each access remains amortized O(1) by showing that the two-tree growth phase uses only direct array offsets and that orphan adoption re-links nodes without re-scanning or re-hashing, preserving the invariant across all |C| augmentations. The added analysis confirms that no hidden logarithmic or linear-in-n factors appear even at n = 10^9. revision: yes

  2. Referee: [§5] §5 (Experimental Evaluation): the claim that the implementation is the fastest available BK code is load-bearing for the practical contribution, yet the reported timings do not isolate the contribution of the compact representation versus low-level tuning; in particular, memory-footprint and cache-miss statistics for the largest graphs are not provided, leaving open whether the observed speed-ups are consistent with the removal of the n factor.

    Authors: We acknowledge that the original experiments did not fully separate the compact representation from low-level tuning. The revised §5 now contains an ablation study that isolates the compact data layout, together with measured memory footprints and L3 cache-miss rates on the largest instances (n ≈ 10^9). These statistics show that the observed speed-ups scale consistently with the elimination of the n factor in the time bound, confirming that the gains are not solely due to micro-optimizations. revision: yes

Circularity Check

0 steps flagged

No circularity; new algorithm and analysis are self-contained

full rationale

The paper derives an improved O(mn|C|) bound for standard BK via direct analysis of its growth, augmentation, and adoption phases, then introduces fcBK with a compact representation claimed to eliminate the n factor while preserving correctness. No step reduces a claimed prediction to a fitted parameter, renames a known result, or relies on a load-bearing self-citation whose validity is internal to the authors. The O(m|C|) claim rests on explicit invariants about constant-time neighbor access in the new encoding, which are stated as implementation properties rather than derived from the result itself. External benchmarks and public code release further separate the analysis from any definitional loop.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper introduces algorithmic improvements on top of standard graph-cut theory without new free parameters or invented entities.

axioms (1)
  • standard math Standard assumptions of the Boykov-Kolmogorov max-flow framework hold for the analyzed graphs.
    The work builds directly on the existing BK algorithm without stating new axioms.

pith-pipeline@v0.9.0 · 5546 in / 1049 out tokens · 36006 ms · 2026-05-14T20:41:44.333762+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

60 extracted references

  1. [1]

    An experimental comparison of min- cut/max-flow algorithms for energy minimization in vision,

    Y . Boykov and V . Kolmogorov, “An experimental comparison of min- cut/max-flow algorithms for energy minimization in vision,”Ieee Trans- actions on Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp. 1124–1137, 2004

    2004

  2. [2]

    Interactive graph cuts for optimal boundary & region segmentation of objects in n-d images,

    Y . Y . Boykov and M. P. Jolly, “Interactive graph cuts for optimal boundary & region segmentation of objects in n-d images,”Proceedings of the Ieee International Conference on Computer Vision, vol. 1, pp. 105–112, 2001

    2001

  3. [3]

    Efficiently solving dynamic markov random fields using graph cuts,

    I. C. SOC, P. Kohli, and P. Torr, “Efficiently solving dynamic markov random fields using graph cuts,”Tenth Ieee International Conference on Computer Vision, Vols 1 and 2, Proceedings, pp. 922–929, 2005

    2005

  4. [4]

    Graph cuts and efficient n-d image segmentation,

    Y . Boykov and G. Funka-Lea, “Graph cuts and efficient n-d image segmentation,”International Journal of Computer Vision, vol. 70, no. 2, pp. 109–131, 2006

    2006

  5. [5]

    Fast approximate energy minimization with label costs,

    A. Delong, A. Osokin, H. N. Isack, and Y . Boykov, “Fast approximate energy minimization with label costs,”International Journal of Com- puter Vision, vol. 96, no. 1, pp. 1–27, 2012

    2012

  6. [6]

    Efficient optimal surface detection: Theory, implementation and experimental validation,

    K. Li, X. Wu, D. Z. Chen, and M. Sonka, “Efficient optimal surface detection: Theory, implementation and experimental validation,”Pro- ceedings of Spie - the International Society for Optical Engineering, vol. 5370, no. 1, pp. 620–627, 2004

    2004

  7. [7]

    3d surface reconstruction using graph cuts with surface constraints,

    S. Tran and L. Davis, “3d surface reconstruction using graph cuts with surface constraints,”Computer Vision - Eccv 2006, Pt 2, Proceedings, vol. 3952, pp. 219–231, 2006

    2006

  8. [8]

    Optimal surface segmentation in volumetric images - a graph-theoretic approach,

    K. Li, X. Wu, D. Z. Chen, and M. Sonka, “Optimal surface segmentation in volumetric images - a graph-theoretic approach,”Ieee Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 1, pp. 119–134, 2006

    2006

  9. [9]

    Multi-camera scene reconstruction via graph cuts,

    V . Kolmogorov and R. Zabih, “Multi-camera scene reconstruction via graph cuts,” inEuropean conference on computer vision. Springer, 2002, pp. 82–96

    2002

  10. [10]

    Efficient multi-view reconstruc- tion of large-scale scenes using interest points, delaunay triangulation and graph cuts,

    P. Labatut, J. P. Pons, and R. Keriven, “Efficient multi-view reconstruc- tion of large-scale scenes using interest points, delaunay triangulation and graph cuts,”Proceedings of the Ieee International Conference on Computer Vision, p. 4408892, 2007

    2007

  11. [11]

    Kolmogorov and zabih’s graph cuts stereo matching algorithm,

    V . Kolmogorov, P. Monasse, and P. Tan, “Kolmogorov and zabih’s graph cuts stereo matching algorithm,”Image Processing On Line, vol. 4, pp. 220–251, 2014

    2014

  12. [12]

    Graph cut-based segmentation for intervertebral disc in human mri,

    L. Silvoster and R. M. S. Kumar, “Graph cut-based segmentation for intervertebral disc in human mri,”Computer Methods in Biomechanics and Biomedical Engineering: Imaging and Visualization, vol. 13, no. 1, p. 2475992, 2025

    2025

  13. [13]

    Atrial scar segmentation via potential learning in the graph-cut framework,

    L. Li, G. Yang, F. Wu, T. Wong, R. Mohiaddin, D. Firmin, J. Keegan, L. Xu, and X. Zhuang, “Atrial scar segmentation via potential learning in the graph-cut framework,”Lecture Notes in Computer Science (including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11395, pp. 152–160, 2019

    2019

  14. [14]

    Supervised and unsupervised segmentation using superpixels, model estimation, and graph cut,

    J. Borovec, J. Švihlík, J. Kybic, and D. Habart, “Supervised and unsupervised segmentation using superpixels, model estimation, and graph cut,”Journal of Electronic Imaging, vol. 26, no. 6, p. 061610, 2017

    2017

  15. [15]

    Conditional gradients for total variation regularization with pde constraints: a graph cuts approach,

    G. Cristinelli, J. A. Iglesias, and D. Walter, “Conditional gradients for total variation regularization with pde constraints: a graph cuts approach,”Computational Optimization and Applications, vol. 93, no. 1, pp. 209–265, 2026

    2026

  16. [16]

    Multimodal style transfer via graph cuts,

    Y . Zhang, C. Fang, Y . Wang, Z. Wang, Z. Lin, Y . Fu, and J. Yang, “Multimodal style transfer via graph cuts,”Proceedings of the Ieee International Conference on Computer Vision, pp. 5942–5950, 2019

    2019

  17. [17]

    Event-based motion segmentation with spatio-temporal graph cuts,

    Y . Zhou, G. Gallego, X. Lu, S. Liu, and S. Shen, “Event-based motion segmentation with spatio-temporal graph cuts,”Ieee Transactions on Neural Networks and Learning Systems, vol. 34, no. 8, pp. 4868–4880, 2023

    2023

  18. [18]

    Graph-cut ransac,

    D. Barath and J. Matas, “Graph-cut ransac,”Proceedings of the Ieee Computer Society Conference on Computer Vision and Pattern Recog- nition, pp. 6733–6741, 2018

    2018

  19. [19]

    Gaussiancut: Interactive segmentation via graph cut for 3d gaussian splatting,

    U. Jain, A. Mirzaei, and I. Gilitschenski, “Gaussiancut: Interactive segmentation via graph cut for 3d gaussian splatting,”Arxiv (cornell University), 2024

    2024

  20. [20]

    An improved boykov’s graph cut-based seg- mentation technique for the efficient detection of cervical cancer,

    M. A. Devi, R. Ezhilarasie, K. S. Joseph, K. Kotecha, A. Abraham, and S. Vairavasundaram, “An improved boykov’s graph cut-based seg- mentation technique for the efficient detection of cervical cancer,”Ieee Access, vol. 11, pp. 77 636–77 647, 2023

    2023

  21. [21]

    Weakly supervised land- cover classification of high-resolution images with low-resolution labels through optimized label refinement,

    Y . Tang, G. Zhang, J. K. Liu, and R. Qin, “Weakly supervised land- cover classification of high-resolution images with low-resolution labels through optimized label refinement,”International Journal of Remote Sensing, vol. 46, no. 5, pp. 1913–1937, 2025

    1913

  22. [22]

    gcdlseg: integrating graph-cut into deep learning for binary semantic segmentation,

    H. Xie, W. Xu, Y . X. Wang, J. Buatti, and X. Wu, “gcdlseg: integrating graph-cut into deep learning for binary semantic segmentation,”Biomed- ical Optics Express, vol. 16, no. 5, pp. 1999–2019, 2025

    1999

  23. [23]

    Deep logismos: Deep learning graph-based 3d segmentation of pancreatic tumors on ct scans,

    Z. Quo, L. Zhang, L. Lu, M. Bagheri, R. M. Summers, M. Sonka, and J. Yao, “Deep logismos: Deep learning graph-based 3d segmentation of pancreatic tumors on ct scans,”Proceedings - International Symposium on Biomedical Imaging, vol. 2018-, pp. 1230–1233, 2018

    2018

  24. [24]

    Maximum flows by incremental breadth-first search,

    A. V . Goldberg, S. Hed, H. Kaplan, R. E. Tarjan, and R. F. Werneck, “Maximum flows by incremental breadth-first search,”Lecture Notes in Computer Science (including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6942, pp. 457– 468, 2011

    2011

  25. [25]

    Faster and more dynamic maximum flow by incremental breadth-first search,

    A. V . Goldberg, S. Hed, H. Kaplan, P. Kohli, R. E. Tarjan, and R. F. Werneck, “Faster and more dynamic maximum flow by incremental breadth-first search,”Lecture Notes in Computer Science (including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9294, pp. 619–630, 2015

    2015

  26. [26]

    Review of serial and parallel min-cut/max-flow algorithms for computer vision,

    P. M. Jensen, N. Jeppesen, A. B. Dahl, and V . A. Dahl, “Review of serial and parallel min-cut/max-flow algorithms for computer vision,” Ieee Transactions on Pattern Analysis and Machine Intelligence, vol. 45, no. 2, pp. 2310–2329, 2023

    2023

  27. [27]

    Cache-efficient graph cuts on structured grids,

    O. Jamriska, D. Sykora, and A. Hornung, “Cache-efficient graph cuts on structured grids,”Proceedings of the Ieee Computer Society Conference on Computer Vision and Pattern Recognition, pp. 3673–3680, 2012

    2012

  28. [28]

    Efficient planar graph cuts with applications in computer vision,

    F. R. Schmidt, E. Töppe, and D. Cremers, “Efficient planar graph cuts with applications in computer vision,”2009 Ieee Conference on Computer Vision and Pattern Recognition, Cvpr 2009, pp. 351–356, 2009

    2009

  29. [29]

    Sparse layered graphs for multi-object segmentation,

    N. Jeppesen, A. N. Christensen, V . A. Dahl, and A. B. Dahl, “Sparse layered graphs for multi-object segmentation,”Proceedings of 2020 Ieee/cvf Conference on Computer Vision and Pattern Recognition, pp. 12 774–12 782, 2020

    2020

  30. [30]

    Graph cut based mesh segmentation using feature points and geodesic distance,

    L. Liu, Y . Sheng, G. Zhang, and H. Ugail, “Graph cut based mesh segmentation using feature points and geodesic distance,”Proceedings - 2015 International Conference on Cyberworlds, Cw 2015, pp. 115–120, 2015

    2015

  31. [31]

    Optimizing binary mrfs via extended roof duality,

    C. Rother, V . Kolmogorov, V . Lempitsky, and M. Szummer, “Optimizing binary mrfs via extended roof duality,”Proceedings of the Ieee Computer Society Conference on Computer Vision and Pattern Recognition, p. 4270228, 2007

    2007

  32. [32]

    The pseudoflow algorithm: A new algorithm for the maximum-flow problem,

    D. S. Hochbaum, “The pseudoflow algorithm: A new algorithm for the maximum-flow problem,”Operations Research, vol. 56, no. 4, pp. 992– 1009, 2008

    2008

  33. [33]

    Simplifications and speedups of the pseudoflow algorithm,

    D. S. Hochbaum and J. B. Orlin, “Simplifications and speedups of the pseudoflow algorithm,”Networks, vol. 61, no. 1, pp. 40–57, 2013

    2013

  34. [34]

    A new approach to the maximum-flow problem,

    A. Goldberg and R. Tarjan, “A new approach to the maximum-flow problem,”Journal of the Acm, vol. 35, no. 4, pp. 921–940, 1988

    1988

  35. [35]

    On implementing the push- relabel method for the maximum flow problem,

    B. V . Cherkassky and A. V . Goldberg, “On implementing the push- relabel method for the maximum flow problem,”Algorithmica (new York), vol. 19, no. 4, pp. 390–410, 1997

    1997

  36. [36]

    An efficient graph cut algorithm for computer vision problems,

    C. Arora, S. Banerjee, P. Kalra, and S. N. Maheshwari, “An efficient graph cut algorithm for computer vision problems,”Lecture Notes in Computer Science (including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6313, no. 3, pp. 552–565, 2010. 14 MIKKELSTRUPet al.: FAST AND COMPACT GRAPH CUTS FOR THE BOYKOV-KO...

    2010

  37. [37]

    The partial augment-relabel algorithm for the max- imum flow problem,

    A. V . Goldberg, “The partial augment-relabel algorithm for the max- imum flow problem,”Lecture Notes in Computer Science (including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5193, pp. 466–477, 2008

    2008

  38. [38]

    Two-level push-relabel algorithm for the maximum flow prob- lem,

    ——, “Two-level push-relabel algorithm for the maximum flow prob- lem,”Lecture Notes in Computer Science (including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5564, pp. 212–225, 2009

    2009

  39. [39]

    Reducing graphs in graph cut segmentation,

    N. Lermé, F. Malgouyres, and L. Létocart, “Reducing graphs in graph cut segmentation,”Proceedings - International Conference on Image Processing, Icip, pp. 3045–3048, 2010

    2010

  40. [40]

    Efficient optimization for hierarchically-structured interacting segments (hints),

    H. Isack, O. Veksler, I. Oguz, M. Sonka, and Y . Boykov, “Efficient optimization for hierarchically-structured interacting segments (hints),” Proceedings - 30th Ieee Conference on Computer Vision and Pattern Recognition, Cvpr 2017, vol. 2017-, pp. 4981–4989, 2017

    2017

  41. [41]

    Paint selection,

    J. Liu, J. Sun, and H. Y . Shum, “Paint selection,”Acm Transactions on Graphics, vol. 28, no. 3, p. 69, 2009

    2009

  42. [42]

    Parallel graph-cuts by adaptive bottom-up merging,

    J. Liu and J. Sun, “Parallel graph-cuts by adaptive bottom-up merging,” Proceedings of the Ieee Computer Society Conference on Computer Vision and Pattern Recognition, pp. 2181–2188, 2010

    2010

  43. [43]

    Fast graph-cut based optimization for practical dense deformable registration of volume images,

    S. Ekström, F. Malmberg, H. Ahlström, J. Kullberg, and R. Strand, “Fast graph-cut based optimization for practical dense deformable registration of volume images,”Computerized Medical Imaging and Graphics, vol. 84, p. 101745, 2020

    2020

  44. [44]

    A cache-aware parallel implementation of the push-relabel network flow algorithm and experimental evaluation of the gap relabeling heuristic,

    D. A. Bader and V . Sachdeva, “A cache-aware parallel implementation of the push-relabel network flow algorithm and experimental evaluation of the gap relabeling heuristic,”18th Isca International Conference on Parallel and Distributed Computing Systems 2005, Pdcs 2005, pp. 41– 48, 2005

    2005

  45. [45]

    A scalable graph-cut algorithm for n-d grids,

    A. Delong and Y . Boykov, “A scalable graph-cut algorithm for n-d grids,”26th Ieee Conference on Computer Vision and Pattern Recog- nition, Cvpr, p. 4587464, 2008

    2008

  46. [46]

    Graph-based algorithms for scene reconstruction from two or more views,

    V . Kolmogorov, “Graph-based algorithms for scene reconstruction from two or more views,” Ph.D. dissertation, Cornell University, 2004

    2004

  47. [47]

    Max-flow problem instances in vision,

    U. of Waterloo, “Max-flow problem instances in vision,” 2025, accessed: Sep. 15, 2025. [Online]. Available: https://vision.cs.uwaterloo.ca/data/ maxflow

    2025

  48. [48]

    Maxflow revisited: An empirical comparison of maxflow algorithms for dense vision problems,

    T. Verma and D. Batra, “Maxflow revisited: An empirical comparison of maxflow algorithms for dense vision problems,”Bmvc 2012 - Electronic Proceedings of the British Machine Vision Conference 2012, pp. 61.1– 61.12, 2012

    2012

  49. [49]

    Computing geodesics and minimal surfaces via graph cuts,

    I. C. SOCIETY , I. C. SOCIETY , Y . Boykov, and V . Kolmogorov, “Computing geodesics and minimal surfaces via graph cuts,”Ninth Ieee International Conference on Computer Vision, Vols I and Ii, Proceedings, pp. 26–33, 2003

    2003

  50. [50]

    Segmentation of trabeculated structures using an anisotropic markov random field: Application to the study of the optic nerve head in glaucoma,

    V . Grau, J. C. Downs, and C. F. Burgoyne, “Segmentation of trabeculated structures using an anisotropic markov random field: Application to the study of the optic nerve head in glaucoma,”Ieee Transactions on Medical Imaging, vol. 25, no. 3, pp. 245–255, 2006

    2006

  51. [51]

    3d virtual histopathology of cardiac tissue from covid-19 patients based on phase-contrast x-ray tomography,

    M. Reichardt, P. M. Jensen, V . A. Dahl, A. B. Dahl, M. Ackermann, H. Shah, F. Länger, C. Werlein, M. P. Kuehnel, D. Jonigk, and T. Salditt, “3d virtual histopathology of cardiac tissue from covid-19 patients based on phase-contrast x-ray tomography,”Elife, vol. 10, p. e71359, 2021

    2021

  52. [52]

    Global optimization for shape fitting,

    V . Lempitsky and Y . Boykov, “Global optimization for shape fitting,” Proceedings of the Ieee Computer Society Conference on Computer Vision and Pattern Recognition, p. 4270318, 2007

    2007

  53. [53]

    Multi-object graph-based segmentation with non-overlapping surfaces,

    P. M. Jensen, A. B. Dahl, and V . A. Dahl, “Multi-object graph-based segmentation with non-overlapping surfaces,”Ieee Computer Society Conference on Computer Vision and Pattern Recognition Workshops, vol. 2020-, pp. 4204–4212, 2020

    2020

  54. [54]

    Learning low- level vision,

    W. T. Freeman, E. C. Pasztor, and O. T. Carmichael, “Learning low- level vision,”International Journal of Computer Vision, vol. 40, no. 1, pp. 25–47, 2000

    2000

  55. [55]

    From photohulls to photoflux opti- mization,

    Y . Boykov and V . Lempitsky, “From photohulls to photoflux opti- mization,”Bmvc 2006 - Proceedings of the British Machine Vision Conference 2006, vol. 3, pp. 1149–1158, 2006

    2006

  56. [56]

    Oriented visibility for multiview reconstruction,

    H. Bischof, V . Lempitsky, Y . Boykov, and D. Ivanov, “Oriented visibility for multiview reconstruction,”Computer Vision - Eccv 2006, Pt 3, Proceedings, vol. 3953, pp. 226–238, 2006

    2006

  57. [57]

    Markov random fields with efficient approximations,

    Y . Boykov, O. Veksler, and R. Zabih, “Markov random fields with efficient approximations,”Proceedings of the Ieee Computer Society Conference on Computer Vision and Pattern Recognition, pp. 648–655, 1998

    1998

  58. [58]

    Computing visual correspondence with occlusions using graph cuts,

    V . Kolmogorov and R. Zabih, “Computing visual correspondence with occlusions using graph cuts,”Proceedings of the Ieee International Conference on Computer Vision, vol. 2, pp. 508–515, 2001

    2001

  59. [59]

    Decision tree fields,

    S. Nowozin, C. Rother, S. Bagon, T. Sharp, B. Yao, and P. Kohli, “Decision tree fields,”Proceedings of the Ieee International Conference on Computer Vision, pp. 1668–1675, 2011

    2011

  60. [60]

    Fusion moves for graph matching,

    L. Hutschenreiter, S. Haller, L. Feineis, C. Rother, D. Kainmüller, and B. Savchynskyy, “Fusion moves for graph matching,”Proceedings of the Ieee International Conference on Computer Vision, vol. 1, pp. 6250– 6259, 2021. MIKKELSTRUPet al.: FAST AND COMPACT GRAPH CUTS FOR THE BOYKOV-KOLMOGOROV ALGORITHM 15 Christian M. Mikkelstrupreceived the B.S.E. degree...

    2021