Wheel inequalities for stable set polytopes
Cheng, Eddie
Cunningham, William H.

Data: 1997
Resum: We introduce new classes of valid inequalities, called wheel inequalities, for the stable set polytope P_G of a graph G. Each "wheel configuration" gives rise to two such inequalities. The simplest wheel configuration is an "odd" subdivision W of a wheel, and for these we give necessary and sufficient conditions for the wheel inequality to be facet-inducing for P_W. Generalizations arise by allowing subdivision paths to intersect, and by replacing the "hub" of the wheel by a clique. The separation problem for these inequalities can be solved in polynomial time. .
Drets: Tots els drets reservats.
Llengua: Anglès
Document: Article ; recerca ; Versió publicada
Publicat a: Mathematical Programming, vol. 77 n. 3 (1997) p. 389-421, ISSN 0025-5610

33 p, 1.7 MB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2023-06-03

   Favorit i Compartir