G-91-36
New Polynomially Solvable Cases for the Maximum Stable Set Problem
BibTeX reference
We describe two new 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. These new classes of graphs are different from the known classes for which the stability number can be computed in polynomial time.
Published September 1991 , 20 pages