کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903038 | 1632399 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Decomposition techniques applied to the Clique-Stable set separation problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In a graph, a Clique-Stable Set separator (CS-separator) is a family C of cuts (bipartitions of the vertex set) such that for every clique K and every stable set S with Kâ©S=â
, there exists a cut (W,Wâ²) in C such that KâW and SâWâ². Starting from a question concerning extended formulations of the Stable Set polytope and a related complexity communication problem, Yannakakis (Yannakakis, 1991) asked in 1991 the following questions: does every graph admit a polynomial-size CS-separator? If not, does every perfect graph do? Several positive and negative results related to this question were given recently. Here we show how graph decomposition can be used to prove that a class of graphs admits a polynomial CS-separator. We apply this method to apple-free graphs and cap-free graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 5, May 2018, Pages 1492-1501
Journal: Discrete Mathematics - Volume 341, Issue 5, May 2018, Pages 1492-1501
نویسندگان
Nicolas Bousquet, Aurélie Lagoutte, Frédéric Maffray, Lucas Pastor,