G-91-40
On a Transformation which Preserves the Stability Number
et référence BibTeX
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.
Paru en octobre 1991 , 17 pages