Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
From MaRDI portal
Publication:3541089
DOI10.1007/978-3-540-87744-8_19zbMath1158.68427MaRDI QIDQ3541089
Publication date: 25 November 2008
Published in: Algorithms - ESA 2008 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-87744-8_19
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
Max-leaves spanning tree is APX-hard for cubic graphs, A new algorithm for finding trees with many leaves, FPT algorithms and kernels for the directed \(k\)-leaf problem, On complexity of minimum leaf out-branching problem, Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems, Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parametrized complexity theory.
- An approximation algorithm for the maximum leaf spanning arborescence problem
- Spanning Trees with Many Leaves
- Minimum Leaf Out-Branching Problems
- Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
- Parameterized Algorithms for Directed Maximum Leaf Problems
- Mathematical Foundations of Computer Science 2003
- Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
- Better Algorithms and Bounds for Directed Maximum Leaf Problems
- Spanning trees with many leaves