Faster Algorithms for Parametric Global Minimum Cut Problems

Hassene Aissi, S. Thomas McCormick, Maurice Queyranne

The parametric global minimum cut problem concerns a graph $G=(V,E)$ where the cost of each edge is an affine function of a parameter $\mu \in {\mathbb{R}}^d$ for some fixed dimension…