SOURCE-LINKED INTELLIGENCE

Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts

arXiv · AI, language, vision and robotics · article · Sep 7, 2026 · UTC

The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges. Over the last years, we engineered a range of fast algorithms for this problem. Our fastest exact algorithm uses an inexact algorithm to obtain a better bound for the problem, reductions that depend on this bound, improved data structures and parallel contraction routines. It is available in the open-source package VieCut and, on real-world instances, outperformed the previously fastest solvers by a factor of up to 2.5 sequentially

Read original source ↗ Open in workspace

recordType

paper

region

Global