Article ID Journal Published Year Pages File Type
431004 Journal of Discrete Algorithms 2012 10 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,