Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
A New Algorithm for Finding Trees with Many Leaves
verfasst von : Joachim Kneis, Alexander Langer, Peter Rossmanith
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.