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

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

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

• An approximation algorithm for the maximum leaf spanning arborescence problem
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• 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?)
• 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 in graphs of minimum degree 4 or 5
• Spanning trees with many leaves
• Spanning Trees with Many Leaves
• The vertex separation number of a graph equals its path-width

Cited in

(16)

• Minimum leaf out-branching and related problems
• Branching in digraphs with many and few leaves: structural and algorithmic results
• Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
• Out-branchings with extremal number of leaves
• Tight bounds and a fast FPT algorithm for directed MAX-leaf spanning tree
• Minimum Leaf Out-Branching Problems
• Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
• On finding directed trees with many leaves
• scientific article; zbMATH DE number 1222099 (Why is no real title available?)
• Spanning directed trees with many leaves
• The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number
• Parameterized Algorithms for Directed Maximum Leaf Problems
• A new algorithm for finding trees with many leaves
• Spanning trees: A survey
• FPT algorithms and kernels for the directed k-leaf problem
• On complexity of minimum leaf out-branching problem

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)