کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1142754 957163 2009 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Stable sets, corner polyhedra and the Chvátal closure
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Stable sets, corner polyhedra and the Chvátal closure
چکیده انگلیسی

We consider the edge formulation of the stable set problem. We characterize its corner polyhedron, i.e. the convex hull of the points satisfying all the constraints except the non-negativity of the basic variables. We show that the non-trivial inequalities necessary to describe this polyhedron can be derived from one row of the simplex tableau as fractional Gomory cuts. It follows that the split closure is not stronger than the Chvátal closure for the edge relaxation of the stable set problem.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 37, Issue 6, November 2009, Pages 375–378
نویسندگان
, ,