کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430630 | 688072 | 2010 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs](/preview/png/430630.png)
چکیده انگلیسی
We study a variation of the vertex cover problem where it is required that the graph induced by the vertex cover is connected. We prove that this problem is polynomial in chordal graphs, has a PTAS in planar graphs, is APX-hard in bipartite graphs and is 5/3-approximable in any class of graphs where the vertex cover problem is polynomial (in particular in bipartite graphs). Finally, dealing with hypergraphs, we study the complexity and the approximability of two natural generalizations.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 8, Issue 1, March 2010, Pages 36–49
Journal: Journal of Discrete Algorithms - Volume 8, Issue 1, March 2010, Pages 36–49
نویسندگان
Bruno Escoffier, Laurent Gourvès, Jérôme Monnot,