Better Algorithms and Bounds for Directed Maximum Leaf Problems

DOI10.1007/978-3-540-77050-3_26MaRDI QIDQ5458844zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

Recommendations

• 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
• On finding directed trees with many leaves
• Parameterized Algorithms for Directed Maximum Leaf Problems

Cites work

• scientific article; zbMATH DE number 16297 (Why is no real title available?)
• scientific article; zbMATH DE number 1305098 (Why is no real title available?)
• scientific article; zbMATH DE number 1016966 (Why is no real title available?)
• scientific article; zbMATH DE number 2080206 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• An approximation algorithm for the maximum leaf spanning arborescence problem
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Interval graphs and searching
• Mathematical Foundations of Computer Science 2003
• On the approximability of some Maximum Spanning Tree Problems
• Parameterized Algorithms for Directed Maximum Leaf Problems
• Parametrized complexity theory.
• Quickly excluding a forest
• Solving Connected Dominating Set Faster Than 2 n
• Spanning Trees with Many Leaves
• Spanning trees in graphs of minimum degree 4 or 5
• Spanning trees with many leaves
• The vertex separation number of a graph equals its path-width

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 and related problems
• Minimum Leaf Out-Branching Problems
• Spanning trees: A survey
• On complexity of minimum leaf out-branching problem
• On finding directed trees with many leaves
• Tight bounds and a fast FPT algorithm for directed MAX-leaf spanning tree
• The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number
• 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)