Stable sets and polynomials (Q1313833)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Stable sets and polynomials |
scientific article |
Statements
Stable sets and polynomials (English)
0 references
1 March 1994
0 references
The author surveys various applications of methods involving nonlinear commutative algebra to the stable set problem for graphs. In particular, he discusses a procedure for generating the facets of the stable set polytope. If a class of graphs \(G\) is such that all the facets of the stable set polytopes can be generated this way in a bounded number of steps, then the stability numbers of these graphs \(G\) are computable in polynomial time. Perfect, \(t\)-perfect, and \(h\)-perfect graphs have this property.
0 references
polynomials
0 references
stable set problem
0 references
facets
0 references
stable set polytope
0 references
stability numbers
0 references
0 references
