On finding spanning trees with few leaves

The problem of finding a spanning tree with few leaves is motivated by the design of communication networks, where the cost of the devices depends on their routing functionality (ending, forwarding, or routing a connection). Besides this application, the problem has its own theoretical importance as a generalization of the Hamiltonian path problem. Lu and Ravi showed that there is no constant factor approximation for minimizing the number of leaves of a spanning tree, unless P=NP. Thus instead of minimizing the number of leaves, we are going to deal with maximizing the number of non-leaves: we give a linear-time 2-approximation for arbitrary graphs, a -approximation for claw-free graphs, and a -approximation for cubic graphs.