کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418470 | 681673 | 2016 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Weighted independent sets in classes of P6P6-free graphs
ترجمه فارسی عنوان
مجموعه های مستقل موزون در کالس های نمودار های آزاد-P6P6
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های گراف. مجموعه مستقل موزون؛ جداساز باند؛ تجزیه مدولار ، نمودار های آزاد P6P6 ؛ نمودار پنجه آزاد
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for P6P6-free graphs, and for S1,2,2S1,2,2-free graphs are unknown. In this note, we give a proof for the solvability of the MWIS problem for (P6P6, S1,2,2S1,2,2, co-chair)-free graphs in polynomial time, by analyzing the structure and the MWIS problem in various subclasses of (P6P6, S1,2,2S1,2,2, co-chair)-free graphs. These results extend some known results in the literature.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 209, 20 August 2016, Pages 217–226
Journal: Discrete Applied Mathematics - Volume 209, 20 August 2016, Pages 217–226
نویسندگان
T. Karthick, Frédéric Maffray,