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.