On the use of Boolean methods for the computation of the stability number (Q1363750)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the use of Boolean methods for the computation of the stability number |
scientific article; zbMATH DE number 1047173
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the use of Boolean methods for the computation of the stability number |
scientific article; zbMATH DE number 1047173 |
Statements
On the use of Boolean methods for the computation of the stability number (English)
0 references
12 January 1998
0 references
The author provides a polynomial time algorithm for the determination of the stability number of a graph which contains neither an induced chordless cycle with four vertices nor its complement. The algorithm is based on the transformation of a graph \(G= (V,E)\) with the above property into a graph \(G'= (V',E')\) with \(|V'|=|V |-1\) and the same stability number. This transformation has been obtained by using pseudo-Boolean techniques. Some applications are given.
0 references
stability number
0 references
0 references
