Graph Substitution and Set Packing Polytopes.
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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 PG, 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 PG that cannot be obtained by lifting a facet of PG - the set x, for any vertex x of G. A necessary and sufficient condition is given for the graphs obtained by Chvatals substitution procedure to be facet producing.
- Operations Research