کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419807 | 683865 | 2012 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Maximum weight independent sets in hole- and dart-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Maximum weight independent sets in hole- and dart-free graphs Maximum weight independent sets in hole- and dart-free graphs](/preview/png/419807.png)
چکیده انگلیسی
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 hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n3)O(n3)-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n4)O(n4)-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issues 16–17, November 2012, Pages 2364–2369
Journal: Discrete Applied Mathematics - Volume 160, Issues 16–17, November 2012, Pages 2364–2369
نویسندگان
M. Basavaraju, L.S. Chandran, T. Karthick,