کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4652449 | 1632596 | 2009 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The Chvátal closure of generalized stable sets in bidirected graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We consider the set of integral solutions of Ax⩽b, x⩾0, where A is the edge-vertex incidence matrix of a bidirected graph. 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 as fractional Gomory cuts. It follows in particular that the split closure is equal to the Chvátal closure in this case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 35, 1 December 2009, Pages 89-95
Journal: Electronic Notes in Discrete Mathematics - Volume 35, 1 December 2009, Pages 89-95