Tight bounds and a fast FPT algorithm for directed Max-Leaf Spanning Tree

DOI10.1145/2000807.2000812zbMath1295.05223OpenAlexW1993219112MaRDI QIDQ3189028

Frederic Dorn, Paul Bonsma

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2000807.2000812

zbMATH Keywords

directed graphsfixed parameter tractablemaximum leaf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (4)

Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ An exact exponential-time algorithm for the directed maximum leaf spanning tree problem ⋮ A new algorithm for finding trees with many leaves ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves

This page was built for publication: Tight bounds and a fast FPT algorithm for directed Max-Leaf Spanning Tree