A fast approximation algorithm for maximum-leaf spanning tree

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 O((m+n)α(m, n)) required by our algorithm is almost linear in the size of G, where m is the number of edged and n is the number of nodes. This improves the previous algorithm by a factor of Ω˜(mn ⁴)