Graph Substitution and Set Packing Polytopes.
Abstract
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' - the set (x)), for any vertex x of G'. A necessary and sufficient condition is given for the graphs obtained by Chvatal's substitution procedure to be facet producing.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1976
- Accession Number
- ADA023853
Entities
People
- Egon Balas
- Eitan Zemel
Organizations
- Carnegie Mellon University