Better Algorithms and Bounds for Directed Maximum Leaf Problems
DOI10.1007/978-3-540-77050-3_26zbMATH Open1135.90416OpenAlexW1499339779MaRDI QIDQ5458844FDOQ5458844
Authors: Noga Alon, Fedor V. Fomin, G. Gutin, Michael Krivelevich, Saket Saurabh 
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
Recommendations
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)
Cites Work
- Spanning trees in graphs of minimum degree 4 or 5
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Quickly excluding a forest
- The vertex separation number of a graph equals its path-width
- Title not available (Why is that?)
- Title not available (Why is that?)
- Interval graphs and searching
- Mathematical Foundations of Computer Science 2003
- Spanning trees with many leaves
- Title not available (Why is that?)
- Parameterized Algorithms for Directed Maximum Leaf Problems
- Solving Connected Dominating Set Faster Than 2 n
Cited In (15)
- Branching in digraphs with many and few leaves: structural and algorithmic results
- A new algorithm for finding trees with many leaves
- Minimum Leaf Out-Branching Problems
- Minimum leaf out-branching and related problems
- Spanning trees: A survey
- On complexity of minimum leaf out-branching problem
- On finding directed trees with many leaves
- The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number
- Tight bounds and a fast FPT algorithm for directed MAX-leaf spanning tree
- FPT algorithms and kernels for the directed \(k\)-leaf problem
- Out-branchings with extremal number of leaves
- Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
- Parameterized Algorithms for Directed Maximum Leaf Problems
- Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
- Spanning directed trees with many leaves
This page was built for publication: Better Algorithms and Bounds for Directed Maximum Leaf Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458844)
