Inhaltszusammenfassung

A stable set in a graph G is a set of pairwise nonadjacent vertices. The problem of finding a maximum weight stable set is one of the most basic NP-hard problems, An important approach to this problem is to formulate it as the problem of optimizing a linear function over the convex hull STAB (G) of incidence vectors of stable sets. Since it is impossible (unless NP = coNP) to obtain a "concise" characterization of STAB(G) as the solution set of a system of linear inequalities, it is a more re...A stable set in a graph G is a set of pairwise nonadjacent vertices. The problem of finding a maximum weight stable set is one of the most basic NP-hard problems, An important approach to this problem is to formulate it as the problem of optimizing a linear function over the convex hull STAB (G) of incidence vectors of stable sets. Since it is impossible (unless NP = coNP) to obtain a "concise" characterization of STAB(G) as the solution set of a system of linear inequalities, it is a more realistic goal to find large classes of valid inequalities with the property that the corresponding separation problem (given a point x*, find, if possible, an inequality in the class that x* violates) is efficiently solvable. Some known large classes of separable inequalities are the trivial, edge, cycle and wheel inequalities. In this paper, we give a polynormial time separation algorithm for the (t)-antiweb inequalities of Trotter. We then introduce an even larger class (in fact, a sequence of classes) of valid inequalities, called (t)-antiweb-s-wheel inequalities. This class is a common generalization of the (t)-antiweb inequalities and the wheel inequalities. We also give efficient separation algorithms for them. » weiterlesen» einklappen

Autoren