A new algorithm for finding trees with many leaves

DOI10.1007/s00453-010-9454-5zbMath1230.68112OpenAlexW2087477484MaRDI QIDQ652536

Alexander Langer, Peter Rossmanith, Joachim Kneis

Publication date: 14 December 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://publications.rwth-aachen.de/record/47970

zbMATH Keywords

graph algorithmsdirected maximum-leaf out-branchingdirected maximum-leaf out-treeout-branchingsout-trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

The \(k\)-leaf spanning tree problem admits a klam value of 39 ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Finding \(k\)-secluded trees faster ⋮ Finding \(k\)-secluded trees faster ⋮ Improved bounds for spanning trees with many leaves ⋮ An exact exponential-time algorithm for the directed maximum leaf spanning tree problem ⋮ Parameterized Complexity of Multi-Node Hubs ⋮ \(k\)-distinct in- and out-branchings in digraphs ⋮ Parameterized complexity of multi-node hubs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• FPT algorithms and kernels for the directed \(k\)-leaf problem
• Solving connected dominating set faster than \(2^n\)
• A short note on the approximability of the maximum leaves spanning tree problem
• Which problems have strongly exponential complexity?
• Graph minors. XIII: The disjoint paths problem
• Tight bounds and a fast FPT algorithm for directed Max-Leaf Spanning Tree
• Spanning Trees with Many Leaves
• Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
• Minimum Leaf Out-Branching Problems
• Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
• Limits and Applications of Group Algebras for Parameterized Problems
• On Finding Directed Trees with Many Leaves
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• On Linear Time Minor Tests with Depth-First Search
• Spanning Directed Trees with Many Leaves
• A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
• Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
• 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
• Digraphs

This page was built for publication: A new algorithm for finding trees with many leaves