The problem of enumerating cut sets in a graph is a problem with a long history, see e.g. . It is well known that graphs may have an exponential number of minimum-weight cuts separating a given pair of vertices . Algorithms for enumerating cuts thus are evaluated w.r.t. to the effort per cut.