کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431004 | 688249 | 2012 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Max-leaves spanning tree is APX-hard for cubic graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider the problem of finding a spanning tree with maximum number of leaves. A 2-approximation algorithm is known for this problem, and a 3/2-approximation algorithm when restricted to graphs where every vertex has degree 3 (cubic graphs). The problem is known to be APX-hard in general, and NP-hard for cubic graphs. We show that it is also APX-hard for cubic graphs. The APX-hardness of the related problem Minimum Connected Dominating Set for cubic graphs follows.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 12, April 2012, Pages 14–23
Journal: Journal of Discrete Algorithms - Volume 12, April 2012, Pages 14–23
نویسندگان
Paul Bonsma,