SIAM Journal on Optimization · 2003 · 39 citations · 17 references
Mathematical ProgrammingStable Set RelaxationsEngineeringComputational Complexity TheoryPlanar GraphComputational ComplexityInitial Upper BoundOdd CircuitExtremal CombinatoricsDiscrete MathematicsCombinatorial OptimizationGeometric Graph TheoryCombinatorial ProblemExtremal Set TheoryComputer ScienceComputational ScienceGraph TheoryComputational ProblemExtremal Graph TheoryTriangle Inequalities
We investigate relaxations for the maximum stable set problem based on the Lovász number $\vartheta(G)$ as an initial upper bound. We strengthen this relaxation by adding two classes of cutting planes, odd circuit and triangle inequalities. We present computational results using this tighter model on many classes of graphs.
17