On cone partitions for the min-cut and max-cut problems with non-negative edges

Andrei V. Nikolaev, Alexander V. Korostil

We consider the classical minimum and maximum cut problems: find a partition of vertices of a graph into two disjoint subsets that minimize or maximize the sum of the weights of ed…