STABLE SETS AND POLYNOMIALS

被引：69

作者：

LOVASZ, L ^{[1
]}

机构：

[1] YALE UNIV,DEPT COMP SCI,NEW HAVEN,CT 06517

来源：

DISCRETE MATHEMATICS | 1994年 / 124卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(92)00057-X

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Several applications of methods from nonlinear algebra to the stable set problem in graphs are surveyed. The most recent work cited was cowritten by A. Schrijver and involves nonlinear inequalities. These yield a procedure to generate facets of the stable set polytope. If a class of graphs has the property that all facets of the stable set polytope can be generated this way in a bounded number of setps, then the stable set problem is polynomially solvable for these graphs. Perfect, t-perfect and h-perfect graphs have this property.

引用

页码：137 / 153

页数：17

共 24 条

[1] COLORINGS AND ORIENTATIONS OF GRAPHS [J].