P435: Enumeration of all small cuts in a graph

P435: Enumeration of all small cuts in a graph

Input:

A weighted graph $G$ and a real number $k > 1$.

Output:

All minimum cuts of weights with less than $k\lambda (G)$ in $G$.

Complexity:

$O(m^2 n + n^{2k}m)$ time for any $k > 1$ and $O(m^2 n + mn^2 \log n)$ time for $k \textless \frac{4}{3}$.

Comment:

$\lambda (G)$ is the weight of a minimum cut of $G$.

Reference:

[Nagamochi1997] (Bibtex)