کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430550 688030 2015 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the maximum independent set problem in subclasses of subcubic graphs
ترجمه فارسی عنوان
در حداکثر مشکل مجموعه مستقل در زیر کلاسهای گرافیکی زیرمجموعه
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

It is known that the maximum independent set problem is NP-complete for subcubic graphs, i.e. graphs of vertex degree at most 3. Moreover, the problem is NP-complete for 3-regular Hamiltonian graphs and for H-free subcubic graphs whenever H contains a connected component which is not a tree with at most 3 leaves. We show that if every connected component of H is a tree with at most 3 leaves and at most 7 vertices, then the problem can be solved for H-free subcubic graphs in polynomial time. We also strengthen the NP-completeness of the problem on 3-regular Hamiltonian graphs by showing that the problem is APX-complete in this class.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 31, March 2015, Pages 104–112
نویسندگان
, , ,