کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141456 | 1489504 | 2013 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Perfectness of clustered graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given a clustered graph (G,V), that is, a graph G=(V,E) together with a partition V of its vertex set, the selective coloring problem consists in choosing one vertex per cluster such that the chromatic number of the subgraph induced by the chosen vertices is minimum. This problem can be formulated as a covering problem with a 0-1 matrix M(G,V). Nevertheless, we observe that, given (G,V), it is NP-hard to check if M(G,V) is conformal (resp. perfect). We will give a sufficient condition, checkable in polynomial time, for M(G,V) to be conformal that becomes also necessary if conformality is required to be hereditary. Finally, we show that M(G,V) is perfect for every partition V if and only if G belongs to a superclass of threshold graphs defined with a complex function instead of a real one.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 10, Issue 4, November 2013, Pages 296-303
Journal: Discrete Optimization - Volume 10, Issue 4, November 2013, Pages 296-303
نویسندگان
Flavia Bonomo, Denis Cornaz, Tınaz Ekim, Bernard Ries,