Generalizations of Cliques, Odd Cycles and Anticycles and their relation to Independence System Polyhedra.

Euler, Reinhardt and Jünger, Michael and Reinelt, Gerhard (1987) Generalizations of Cliques, Odd Cycles and Anticycles and their relation to Independence System Polyhedra.
Published in: Mathematics of Operations Research Vol. 12 (3). pp. 451-462. ISSN 0364-765X

Abstract

Padberg [1973] has shown that if a graph G with vertex set V constitutes a clique (odd cycle, odd anticycle), then the inequality Σ[sub x, ∈, V] x[sub v] ≤ 1 (Σ [sub x, ∈ V] x[sub v] ≤ ½(|V| - 1), Σ[sub x, ∈, V] x[sub v] ≤ 2) defines a facet of P(G[sub ST](G)), the convex hull of the incidence vectors of stable sets in G. We generalize the concepts of cliques, odd cycles and anticycles to arbitrary independence systems (E, G) and show that the corresponding inequalities define facets of P(G), the convex hull of the incidence vectors of independent sets.


Actions:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: UNSPECIFIED
Depositing User: Archive Admin
Date Deposited: 31 Aug 2010 14:44
Last Modified: 04 Jul 2014 09:31
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/814