A linear-time kernelization for the rooted \(k\)-leaf outbranching problem

DOI10.1016/j.dam.2015.04.028zbMath1317.05072OpenAlexW415013543MaRDI QIDQ2354724

Frank Kammer

Publication date: 24 July 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.04.028

zbMATH Keywords

parameterized complexitylinear-time data reductionNP-hard graph problemsdominator trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

Fixed-parameter algorithms for DAG partitioning

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• A more effective linear kernelization for cluster editing
• Applying modular decomposition to parameterized cluster editing problems
• Vertex Cover: Further Observations and Further Improvements
• A Linear-Time Kernelization for the Rooted k-Leaf Outbranching Problem
• Simpler Linear-Time Kernelization for Planar Dominating Set
• Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs
• Streaming Kernelization
• Kernel(s) for problems with no kernel
• On Finding Directed Trees with Many Leaves
• Vertex packings: Structural properties and algorithms
• Dominators in Linear Time
• Efficient Parameterized Preprocessing for Cluster Editing
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: A linear-time kernelization for the rooted \(k\)-leaf outbranching problem