2008 | OriginalPaper | Chapter
A New Algorithm for Finding Trees with Many Leaves
Authors : Joachim Kneis, Alexander Langer, Peter Rossmanith
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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({\it poly}(|V|) + 4^k k^2)$
on undirected graphs, and
O
(4
k
|
V
| ·|
E
|) on directed graphs. This improves over the previously fastest algorithms for these problems with run times of
$O({\it poly}(|V|) + 6.75^k {\it poly}(k))$
and
$2^{O(k \log k)} {\it poly}(|V|)$
, respectively.