Accession Number:

ADA023853

Title:

Graph Substitution and Set Packing Polytopes.

Descriptive Note:

Research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1976-01-01

Pagination or Media Count:

29.0

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 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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE