Critical Cutsets of Graphs and Canonical Facets of Set Packing Polytopes.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1976
- Accession Number
- ADA023854
Entities
People
- Egon Balas
- Eitan Zemel
Organizations
- Carnegie Mellon University