کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10331916 686963 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Addendum to: Maximum Weight Independent Sets in hole- and co-chair-free graphs
ترجمه فارسی عنوان
افزودن به: حداکثر وزن مجموعه های مستقل در نمودار سوراخ و کم صندلی
کلمات کلیدی
الگوریتم های گراف، مشکل کمترین وزن مستقل مجموعه، تجزیه کننده جداساز کلاسیک، تجزیه مدولار، نمودارهای عجیب و غریب، نمودارهای کامل،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In Brandstädt and Giakoumakis [2], we reduce the Maximum Weight Independent Set (MWIS) problem on hole- and co-chair-free graphs to a corresponding problem on prime atoms. Here we refine these results by investigating atoms of prime graphs (avoiding the requirement that the graphs are prime and atoms) and also observe that the MWIS problem is solvable in polynomial time on (odd-hole, co-chair)-free graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 345-350
نویسندگان
, ,