| Resumen: |
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. . |
visitante ::
identificación
Acceso restringido a la UAB
