On graphs of the cone decompositions for the min-cut and max-cut problems (Q1751487)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On graphs of the cone decompositions for the min-cut and max-cut problems |
scientific article; zbMATH DE number 6873326
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On graphs of the cone decompositions for the min-cut and max-cut problems |
scientific article; zbMATH DE number 6873326 |
Statements
On graphs of the cone decompositions for the min-cut and max-cut problems (English)
0 references
25 May 2018
0 references
Summary: 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.
0 references
clique number, time complexity
0 references
