کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1143320 957191 2011 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the facets of the stable set polytope of quasi-line graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the facets of the stable set polytope of quasi-line graphs
چکیده انگلیسی
While the Ben Rebea Theorem provides a complete linear description of the stable set polytope of quasi-line graphs, no minimal description is currently available. In this paper, we shed some light on this question by (1) showing that any facet of this polytope is such that the restriction of the inequality to maximal coefficients yields a rank facet and (2) providing a complete description of the strongly minimal facets. We also show that those results support two conjectures refining the Ben Rebea Theorem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 39, Issue 3, May 2011, Pages 208-212
نویسندگان
,