Geodesic
Polyhedral Graphs of GRAPH PARTITIONING and COMPLETE BIPARTITE SUBGRAPH Problems
Modelirovanie i analiz informacionnyh sistem, Tome 19 (2012) no. 6, pp. 101-106.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: polyhedra of combinatorial problems, adjacency of vertices, clique number of graph of polyhedron. 
@article{MAIS_2012_19_6_a8,
     author = {A. I. Antonov and V. A. Bondarenko},
     title = {Polyhedral {Graphs} of {GRAPH} {PARTITIONING} and {COMPLETE} {BIPARTITE} {SUBGRAPH} {Problems}},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {101--106},
     publisher = {mathdoc},
     volume = {19},
     number = {6},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2012_19_6_a8/}
}
TY  - JOUR
AU  - A. I. Antonov
AU  - V. A. Bondarenko
TI  - Polyhedral Graphs of GRAPH PARTITIONING and COMPLETE BIPARTITE SUBGRAPH Problems
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2012
SP  - 101
EP  - 106
VL  - 19
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2012_19_6_a8/
LA  - ru
ID  - MAIS_2012_19_6_a8
ER  - 
%0 Journal Article
%A A. I. Antonov
%A V. A. Bondarenko
%T Polyhedral Graphs of GRAPH PARTITIONING and COMPLETE BIPARTITE SUBGRAPH Problems
%J Modelirovanie i analiz informacionnyh sistem
%D 2012
%P 101-106
%V 19
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2012_19_6_a8/
%G ru
%F MAIS_2012_19_6_a8
A. I. Antonov; V. A. Bondarenko. Polyhedral Graphs of GRAPH PARTITIONING and COMPLETE BIPARTITE SUBGRAPH Problems. Modelirovanie i analiz informacionnyh sistem, Tome 19 (2012) no. 6, pp. 101-106. http://geodesic.mathdoc.fr/item/MAIS_2012_19_6_a8/

[1] V. A. Bondarenko, A. N. Maksimenko, Geometricheskie konstruktsii i slozhnost v kombinatornoi optimizatsii, LKI, M., 2008, 184 pp.

[2] M. Geri, D. Dzhonson, Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR