کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656815 | 1632985 | 2014 | 28 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are GG-perfect
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are GG-perfect The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are GG-perfect](/preview/png/4656815.png)
چکیده انگلیسی
In [6], Edmonds provided the first complete description of the polyhedron associated with a combinatorial optimization problem: the matching polytope. As the matching problem is equivalent to the stable set problem on line graphs, many researchers tried to generalize Edmonds' result by considering the stable set problem on a superclass of line graphs: the claw-free graphs. However, as testified also by Grötschel, Lovász, and Schrijver [14], “in spite of considerable efforts, no decent system of inequalities describing STAB(G)STAB(G)for claw-free graphs is known”.Here, we provide an explicit linear description of the stable set polytope of claw-free graphs with stability number at least four and with no 1-join.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 108, September 2014, Pages 1–28
Journal: Journal of Combinatorial Theory, Series B - Volume 108, September 2014, Pages 1–28
نویسندگان
A. Galluccio, C. Gentile, P. Ventura,