| Date: |
1997 |
| Abstract: |
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. . |
| Rights: |
Aquest material està protegit per drets d'autor i/o drets afins. Podeu utilitzar aquest material en funció del que permet la legislació de drets d'autor i drets afins d'aplicació al vostre cas. Per a d'altres usos heu d'obtenir permís del(s) titular(s) de drets.  |
| Language: |
Anglès |
| Document: |
Article ; recerca ; Versió publicada |
| Subject: |
Matemàtica |
| Published in: |
Mathematical Programming, vol. 77 n. 3 (1997) p. 389-421, ISSN 0025-5610 |
guest ::
UAB restricted access
