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 the normal view instead:
scientific article; zbMATH DE number 6873326
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.8061219453811646
0 references
0.7902308106422424
0 references
