On Graphs of the Cone Decompositions for the Min-Cut and Max-Cut Problems

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.

from #AlexandrosSfakianakis via Alexandros G.Sfakianakis on Inoreader http://ift.tt/1nzCycE
via IFTTT