Accession Number:

ADA023854

Title:

Critical Cutsets of Graphs and Canonical Facets of Set Packing Polytopes.

Descriptive Note:

Research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1976-02-01

Pagination or Media Count:

15.0

Abstract:

A cutset in a graph G with node set N is the set of edges joining the nodes in a subset of N to those not in the subset. A cutset is called critical if its removal produces a graph whose independence number is greater than that of G. The concept of a critical cutset is used to give first a necessary, then a sufficient condition for an inequality with 0-1 coefficients to be a facet of the set packing polytope defined by G.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE