2 papers
cs.DS2026
Optimality-Preserving Data Reduction for Maximum k-Cut (Full Version)
Michael Kaibel, Petra Mutzel
Preprocessing has become an increasingly important part of solving Maximum Cut to optimality, enabling exact solvers to tackle significantly larger instances. This suggests that ex…
cs.DS2024
A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order
Arne Beines, Michael Kaibel, Philip Mayer +2
We present parametric breadth-first search (PBFS), a new algorithm for solving the parametric minimum cut problem in a network with source-sink-monotone capacities. The objective i…