On Graphs of the Cone Decompositions for the Min-Cut and Max-Cut Problems
В. А. Бондаренко, Andrei V. Nikolaev · International Journal of Mathematics and Mathematical Sciences · 2016
We consider maximum and minimum cut problems with nonnegative weights of edges. We define the graphs of the cone decompositions and find a linear clique number for the min-cut problem and a superpolynomial clique number for the max-cut problem. These values characterize the time complexity in a broad class of algorithms based on linear comparisons.