Wheel inequalities for stable set polytopes

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
Matèria:	Matemàtica
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

Registre creat el 2006-03-13, darrera modificació el 2024-05-02