FPT algorithms and kernels for the directed k-leaf problem
DOI10.1016/J.JCSS.2009.06.005zbMATH Open1184.05120OpenAlexW2138156539MaRDI QIDQ847265FDOQ847265
Authors: Jean Daligault, G. Gutin, Eun Jung Kim, A. Yeo 
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
Recommendations
- FPT and kernelization algorithms for the induced tree problem
- scientific article; zbMATH DE number 2080206
- 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
- Better Algorithms and Bounds for Directed Maximum Leaf Problems
- Parameterized Algorithms for Directed Maximum Leaf Problems
- scientific article; zbMATH DE number 7310159
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
- A faster exact algorithm for the directed maximum leaf spanning tree problem
- A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
kerneldigraphfixed-parameter tractableleavesdirected max leaf problemout-branching subgraphrooted directed k-leaf problem
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?)
- Title not available (Why is that?)
- Spanning directed trees with many leaves
- Solving connected dominating set faster than \(2^n\)
- Mathematical Foundations of Computer Science 2003
- Spanning trees with many leaves
- Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
- A New Algorithm for Finding Trees with Many Leaves
- On Problems without Polynomial Kernels (Extended Abstract)
- Title not available (Why is that?)
- Parameterized Algorithms for Directed Maximum Leaf Problems
- Better Algorithms and Bounds for Directed Maximum Leaf Problems
Cited In (21)
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- A new algorithm for finding trees with many leaves
- An exact algorithm for the maximum leaf spanning tree problem
- \(k\)-distinct in- and out-branchings in digraphs
- \(k\)-distinct in- and out-branchings in digraphs
- Enumerate and measure: improving parameter budget management
- A linear-time kernelization for the rooted \(k\)-leaf outbranching problem
- On finding directed trees with many leaves
- Basic Terminology, Notation and Results
- The complexity of finding arc-disjoint branching flows
- A linear-time kernelization for the rooted \(k\)-leaf outbranching problem
- An exact exponential-time algorithm for the directed maximum leaf spanning tree problem
- On the directed full degree spanning tree problem
- Parameterized algorithms for non-separating trees and branchings in digraphs
- The \(k\)-leaf spanning tree problem admits a klam value of 39
- Balanced branchings in digraphs
- Title not available (Why is that?)
- Complexity of independency and cliquy trees
- Improved kernel results for some FPT problems based on simple observations
- A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
- Parameterized measure \& conquer for problems with no small kernels
This page was built for publication: FPT algorithms and kernels for the directed \(k\)-leaf problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q847265)
