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 3/2-approximation for claw-free graphs, and a 6/5-approximation for cubic graphs. (c) 2007 Elsevier B.V. All fights reserved.