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


On a Transformation which Preserves the Stability Number


We derive from Boolean methods a transformation which, when it can be applied, builds from a graph G = (V,E) a new graph G'= (V',E') with the same stability number and such that |V'| = |V| - 1. We next describe a class of graphs for which such a transformation leads to polynomial algorithm for computing the stability number.

, 17 pages