I am trying to find an algorithm that would give me for a given graph all minimal cut sets or equivalently all ways to partition the graph in two connected components. I am searching for an algorithm that ideally would have the complexity linear in the number of cut sets, however, I only find papers describing algorithms that would generate all minimal cut sets between a fixed vertex pair. I would then have to run any algorithm for each pair and remove duplicates, so I am searching for a better approach. Does someone of you know any upper/lower bounds of the complexity of this problem (or even better, an optimal algorithm)? I would also be interested in results concerning special graphs, e.g. max degree k or so.