Open AccessPolyhedral Graphs of GRAPH PARTITIONING and COMPLETE BIPARTITE SUBGRAPH Problems
Author(s) -
Анатолий Игоревич Антонов,
В. А. Бондаренко
Publication year - 2015
Publication title -
modelirovanie i analiz informacionnyh sistem
Language(s) - English
Resource type - Journals
eISSN - 2313-5417
pISSN - 1818-1015
DOI - 10.18255/1818-1015-2012-6-101-106
Subject(s) - bipartite graph , combinatorics , induced subgraph isomorphism problem , cograph , complete bipartite graph , split graph , mathematics , simplex graph , block graph , clique graph , distance hereditary graph , discrete mathematics , clique , subgraph isomorphism problem , induced subgraph , line graph , graph , pathwidth , voltage graph , vertex (graph theory)
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.