文章基本信息

标题：On Graphs of the Cone Decompositions for the Min-Cut and Max-Cut Problems
本地全文：下载
作者：Vladimir Bondarenko ; Andrei Nikolaev
期刊名称：International Journal of Mathematics and Mathematical Sciences
印刷版ISSN：0161-1712
电子版ISSN：1687-0425
出版年度：2016
卷号：2016
DOI：10.1155/2016/7863650
出版社：Hindawi Publishing Corporation
摘要：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.