Polynomially solvable cases for the maximum stable set problem
Authors:
Alain Hertz
Affiliation:
Ecole Poly. Fédérale de Lausanne, Département de Mathématiques, MA (Ecublens), CH-1015, Lausanne, Switzerland
Abstract:
We describe two classes of graphs for which the stability number can be computed in polynomial time. The first approach is based on an iterative procedure which, at each step, builds from a graph G a new graph G′ which has fewer vertices and has the property that (G′) = (G) − 1. For the second class, it can be decided in polynomial time whether there exists a stable set of given size k.