Polyhedral Graphs of GRAPH PARTITIONING and COMPLETE BIPARTITE SUBGRAPH Problems
https://doi.org/10.18255/1818-1015-2012-6-101-106
Abstract
We provide an effective description of graphs of polyhedra for GRAPH PARTITIONING and COMPLETE BIPARTITE SUBGRAPH problems. We establish the fact, that the clique number for each of this problems increases exponentially with the dimension of the space.
About the Authors
A. I. Antonov
Ярославский государственный университет им. П.Г. Демидова
Russian Federation
аспирант
Russian Federation
аспирант
V. A. Bondarenko
Ярославский государственный университет им. П.Г. Демидова
Russian Federation
д-р физ.-мат. наук, профессор, заведующий кафедрой дискретного анализа
Russian Federation
д-р физ.-мат. наук, профессор, заведующий кафедрой дискретного анализа
References
1. Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. М.: ЛКИ, 2008. 184 с.
2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
Review
For citations:
Antonov A.I., Bondarenko V.A. Polyhedral Graphs of GRAPH PARTITIONING and COMPLETE BIPARTITE SUBGRAPH Problems. Modeling and Analysis of Information Systems. 2012;19(6):101-106. (In Russ.) https://doi.org/10.18255/1818-1015-2012-6-101-106
Views:
933
Email this article 