Suboptimal cuts – their enumeration, weight and number

We present (1) an algorithm that enumerates the cuts of a network by increasing weight with polynomial delay, and (2) an algorithm that computes the k-th minimum weight in polynomial time for fixed k. We also show that in the case of undirected networks there are only polynomially many cuts that have the k-th minimum weight for any fixed k (whereas directed networks can have exponentially many different minimum cuts).