|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
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.