  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 $d$. We consider the problems of finding
the next breakpoint in a given direction, and finding a parameter value with
maximum minimum cut value. We develop strongly polynomial algorithms for these
problems that are faster than a naive application of Megiddo's parametric
search technique. Our results indicate that the next breakpoint problem is
easier than the max value problem.
