A new algorithm for finding trees with many leaves

DOI10.1007/S00453-010-9454-5MaRDI QIDQ652536zbMATH OpenOpenAlexFDO

Authors Joachim Kneis, Alexander Langer, Peter Rossmanith

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

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

Recommendations

• A New Algorithm for Finding Trees with Many Leaves
• On finding directed trees with many leaves
• Spanning directed trees with many leaves
• Better Algorithms and Bounds for Directed Maximum Leaf Problems
• A faster exact algorithm for the directed maximum leaf spanning tree problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305098 (Why is no real title available?)
• scientific article; zbMATH DE number 2080206 (Why is no real title available?)
• scientific article; zbMATH DE number 806748 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
• A short note on the approximability of the maximum leaves spanning tree problem
• An approximation algorithm for the maximum leaf spanning arborescence problem
• Better Algorithms and Bounds for Directed Maximum Leaf Problems
• Digraphs
• FPT algorithms and kernels for the directed k-leaf problem
• Graph minors. XIII: The disjoint paths problem
• Limits and Applications of Group Algebras for Parameterized Problems
• Mathematical Foundations of Computer Science 2003
• Minimum Leaf Out-Branching Problems
• On Linear Time Minor Tests with Depth-First Search
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• On finding directed trees with many leaves
• Parameterized Algorithms for Directed Maximum Leaf Problems
• Solving connected dominating set faster than \(2^n\)
• Spanning Trees with Many Leaves
• Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
• Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
• Spanning directed trees with many leaves
• Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
• Tight bounds and a fast FPT algorithm for directed MAX-leaf spanning tree
• Which problems have strongly exponential complexity?
• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves

Cited in

(15)

• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Improved bounds for spanning trees with many leaves
• Mathematical Foundations of Computer Science 2003
• k-distinct in- and out-branchings in digraphs
• Finding \(k\)-secluded trees faster
• Finding \(k\)-secluded trees faster
• Spotting trees with few leaves
• Spotting trees with few leaves
• On finding directed trees with many leaves
• An exact exponential-time algorithm for the directed maximum leaf spanning tree problem
• Parameterized complexity of multi-node hubs
• The \(k\)-leaf spanning tree problem admits a klam value of 39
• A faster exact algorithm for the directed maximum leaf spanning tree problem
• A New Algorithm for Finding Trees with Many Leaves
• Parameterized complexity of multi-node hubs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q652536)