Computational Experience with Stable Set Relaxations
Gerald Gruber, Franz Rendl
We investigate relaxations for the maximum stable set problem based on
the Lovasz 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.
Research Report, Department of Mathematics,
University of Klagenfurt, Austria, December 2000
Contact: [email protected]