On Graphs of the Cone Decompositions for the Min-Cut and Max-Cut Problems
Joint Authors
Bondarenko, Vladimir
Nikolaev, Andrei
Source
International Journal of Mathematics and Mathematical Sciences
Issue
Vol. 2016, Issue 2016 (31 Dec. 2016), pp.1-6, 6 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2016-02-01
Country of Publication
Egypt
No. of Pages
6
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Bondarenko, Vladimir& Nikolaev, Andrei. 2016. On Graphs of the Cone Decompositions for the Min-Cut and Max-Cut Problems. International Journal of Mathematics and Mathematical Sciences،Vol. 2016, no. 2016, pp.1-6.
https://search.emarefa.net/detail/BIM-1106326
Modern Language Association (MLA)
Bondarenko, Vladimir& Nikolaev, Andrei. On Graphs of the Cone Decompositions for the Min-Cut and Max-Cut Problems. International Journal of Mathematics and Mathematical Sciences No. 2016 (2016), pp.1-6.
https://search.emarefa.net/detail/BIM-1106326
American Medical Association (AMA)
Bondarenko, Vladimir& Nikolaev, Andrei. On Graphs of the Cone Decompositions for the Min-Cut and Max-Cut Problems. International Journal of Mathematics and Mathematical Sciences. 2016. Vol. 2016, no. 2016, pp.1-6.
https://search.emarefa.net/detail/BIM-1106326
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1106326