Paper Info
Title
Max-leaves spanning tree is APX-hard for cubic graphs
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.
Year
DOI
Venue
2009
10.1016/j.jda.2011.06.005
J. Discrete Algorithms
Keywords
DocType
Volume
minimum connected dominating set,maximum leaf,cubic graph,apx-hard,2-approximation algorithm,related problem,approximation algorithm,maximum number,spanning tree,computational complexity,apx hard,data structure,discrete mathematics
Journal
12,
ISSN
Citations 
PageRank 
Journal of Discrete Algorithms
5
0.44
References 
Authors
21
1
Name
Order
Citations
PageRank
Paul Bonsma128720.46