Premium
Graph substitution and set packing polytopes
Author(s) -
Balas E.,
Zemel E.
Publication year - 1977
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230070307
Subject(s) - polytope , combinatorics , facet (psychology) , vertex (graph theory) , mathematics , graph , set (abstract data type) , set packing , discrete mathematics , computer science , psychology , social psychology , personality , big five personality traits , programming language
Facets of the set packing polytope provide strong cutting planes for set packing and partitioning problems. Set packing polytopes are in a one‐to‐one correspondence with graphs. The facets of P(G), the set packing polytope associated with the graph G, are related to certain subgraphs of G. Of particular interest are those subgraphs G′ which are facet producing, i.e., which give rise to facets of P(G′) that cannot be obtained by lifting a facet of P(G′ ‐ {x}), for any vertex x of G′. In this paper we characterize the facets of the set packing polytopes associated with the class of graphs obtained by Chvátal's substitution procedure, and give necessary and sufficient conditions for these graphs to be facet‐producing.