Abstract
Given an undirected graph G, finding a spanning tree of G with maximum number of leaves is not only NP-complete but also MAX~SNP-complete. The approximation ratio of the previously best known approximation algorithm for maximum leaf spanning tree is three. However, the high-order running time required by the previous algorithm makes it impractical. In this paper we give a new factor-three approximation algorithm for the same problem. The running time required by our algorithm is almost linear in the size of G. This improves the previous algorithm by a factor of \tilde{\Omega}(mn^4), where n is the number of nodes and m is the number of edges.