Stable sets and polynomials (Q1313833)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 500614
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Stable sets and polynomials |
scientific article; zbMATH DE number 500614 |
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
0 references
0 references
0 references
0.9065553
0 references
0 references
