Better Algorithms and Bounds for Directed Maximum Leaf Problems

DOI10.1007/978-3-540-77050-3_26zbMath1135.90416OpenAlexW1499339779MaRDI QIDQ5458844

Fedor V. Fomin, Saket Saurabh, Noga Alon, Michael Krivelevich, Gregory Gutin

Publication date: 24 April 2008

Published in: FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77050-3_26

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

FPT algorithms and kernels for the directed \(k\)-leaf problem ⋮ Minimum Leaf Out-Branching Problems ⋮ A new algorithm for finding trees with many leaves ⋮ Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree ⋮ Spanning trees: A survey ⋮ Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Interval graphs and searching
• Quickly excluding a forest
• Spanning trees in graphs of minimum degree 4 or 5
• The vertex separation number of a graph equals its path-width
• On the approximability of some Maximum Spanning Tree Problems
• Parametrized complexity theory.
• An approximation algorithm for the maximum leaf spanning arborescence problem
• Spanning Trees with Many Leaves
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Solving Connected Dominating Set Faster Than 2 n
• Parameterized Algorithms for Directed Maximum Leaf Problems
• Mathematical Foundations of Computer Science 2003
• Spanning trees with many leaves

This page was built for publication: Better Algorithms and Bounds for Directed Maximum Leaf Problems