FPT algorithms and kernels for the directed \(k\)-leaf problem

DOI10.1016/j.jcss.2009.06.005zbMath1184.05120MaRDI QIDQ847265

Gregory Gutin, Anders Yeo, Jean Daligault, Eun Jung Kim

Publication date: 12 February 2010

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2009.06.005

zbMATH Keywords

digraph; kernel; fixed-parameter tractable; leaves; directed max leaf problem; out-branching subgraph; rooted directed k-leaf problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

The complexity of finding arc-disjoint branching flows, Parameterized algorithms for non-separating trees and branchings in digraphs, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, An exact exponential-time algorithm for the directed maximum leaf spanning tree problem, On the directed full degree spanning tree problem, A 2-approximation algorithm for finding a spanning tree with maximum number of leaves, A new algorithm for finding trees with many leaves, An exact algorithm for the maximum leaf spanning tree problem, The \(k\)-leaf spanning tree problem admits a klam value of 39, Parameterized measure \& conquer for problems with no small kernels, Balanced branchings in digraphs, Enumerate and Measure: Improving Parameter Budget Management, On Finding Directed Trees with Many Leaves

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving connected dominating set faster than \(2^n\)
• 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
• On Problems without Polynomial Kernels (Extended Abstract)
• Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
• A New Algorithm for Finding Trees with Many Leaves
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Spanning Directed Trees with Many Leaves
• Parameterized Algorithms for Directed Maximum Leaf Problems
• Mathematical Foundations of Computer Science 2003
• Better Algorithms and Bounds for Directed Maximum Leaf Problems
• Spanning trees with many leaves