کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421114 684142 2015 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Computational complexity of minimum P4P4 vertex cover problem for regular and K1,4K1,4-free graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Computational complexity of minimum P4P4 vertex cover problem for regular and K1,4K1,4-free graphs
چکیده انگلیسی

In VCP4 problem, it is asked to find a set S⊆VS⊆V of minimum size such that G[V∖S]G[V∖S] contains no path on 4 vertices, in a given graph G=(V,E)G=(V,E). We prove that it is APX-complete for 3-regular graphs as well as 3-regular bipartite graphs. We show that a greedy based algorithm approximates VCP4 within a factor of 2 for regular graphs. We also show that VCP4 is APX-complete for K1,4K1,4-free graphs and a local ratio based algorithm generates a solution which is within a factor of 3.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 184, 31 March 2015, Pages 114–121
نویسندگان
, , ,