Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree

DOI10.1007/978-3-540-87744-8_19zbMath1158.68427MaRDI QIDQ3541089

Frederic Dorn, Paul Bonsma

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

Mathematics Subject Classification ID

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