Groupe d’études et de recherche en analyse des décisions


On the Stability Number of AH-Free Graphs


We describe a new class of graphs for which the stability number can be obtained in polynomial time. The algorithm is based on an iterative procedure which, at each step, builds from a graph G a new graph G' which has fewer nodes and has the property that (G') = (G) - 1.

, 18 pages