کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431004 688249 2012 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Max-leaves spanning tree is APX-hard for cubic graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Max-leaves spanning tree is APX-hard for cubic graphs
چکیده انگلیسی

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
نویسندگان
,