A New Algorithm for Finding Trees with Many Leaves
Joachim Kneis, Alexander Langer, Peter Rossmanith
We present an algorithm that finds trees with at least k leaves in
undirected and directed graphs. These problems are known as Maximum
Leaf Spanning Tree for undirected graphs, and, respectively, Directed
Maximum Leaf Out-Tree and Directed Maximum Leaf Spanning Out-Tree in
the case of directed graphs.
The run time of our algorithm is O(poly(|V|) + 4^k k^2) on undirected
graphs, and O(4^k |V| |E|) on directed graphs. Currently, the fastest
algorithms for these problems have run times of O(poly(n) + 6.75^k
poly(k)) and 2^{O(k log k)} poly(n), respectively.