Abstract of Paper

A faster FPT algorithm for finding spanning trees with many leaves
by P.S. Bonsma and T. Brueggemann and G.J. Woeginger

Abstract:

We describe a new, fast, and fairly simple FPT algorithm for the problem of
deciding whether a given input graph G has a spanning tree with at least k
leaves. The time complexity of our algorithm is polynomially bounded in the
size of G, and its dependence on k is roughly $O(9.49^k)$. This yields the
fastest currently known FPT algorithm for the max-leaf spanning tree
problem.