A Near-linear-time Approximation Algorithm for Maximum-leaf Spanning Tree
Hsueh Lu, R. Ravi · 1996
Given an undirected graph G, finding a spanning tree of G with maximum number of leaves is not only NP-complete [11] but also MAX SNP-complete [10]. The approximation ratio of the previously best known approximation algorithm for maximum leaf spanning tree is three [19]. 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)ff(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 ~ \\Omega\\Gamma mn 4 ).