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 is the fastest currently known algorithm for this problem.
|Title of host publication||Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'2003, Bratislava, Slovakia, August 25-29, 2003)|
|Editors||B. Rovan, P. Vojtás|
|Place of Publication||Berlin|
|Publication status||Published - 2003|
|Name||Lecture Notes in Computer Science|